[백준 - 14501] 퇴사 [C++]

1. 문제

https://www.acmicpc.net/problem/14501

14501번: 퇴사

2. 풀이과정

백준이가 상담을 잡을 수 있는 모든 경우에 대해 수익을 계산해 최대 수익을 구한다.

 

입력예시

위와 같은 입력을 예로 들면

(1일, 4일, 5일)

(1일, 5일)

(2일)

(3일, 4일, 5일)

(3일, 5일)

       .

       .

 

와 같은 순서로 상담을 잡을 수 있는 모든 경우를 따져보면 된다.

[코드설명]

dfs함수는 상담을 잡을 수 있는 모든 경우에 대해 최대수익을 갱신해준다. 

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
vector<int> T, P;
bool visited[17];
int max_v = -1;

void dfs(int sum, int curr) {
    if(curr && curr + T[curr] - 1 == n) {
        max_v = max(max_v, sum);
        return ;
    }
    if(curr && curr + T[curr] - 1 > n) {
        max_v = max(max_v, sum-P[curr]);
        return ;
    }
    int start = curr ? curr + T[curr] : 1;
    for(int i=start; i<=n; i++) {
        if(!visited[i]) {
            visited[i] = true;
            dfs(sum+P[i], i);
            visited[i] = false;
        }
    } 
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n;
    T.resize(n+1);
    P.resize(n+1);
    for(int i=1; i<=n; i++) {
        cin >> T[i] >> P[i];
    }
    dfs(0, 0);
    cout << max_v;
    return 0;
}