백준 14501번 퇴사 문제 풀이

완전탐색으로 풀면 된다.

 

dfs로 모든 경우를 모두 체크하면 되며 재귀함수호출로 구현하면 간단하다.

 

dfs(int day) 함수는 day번째 날 부터 최대 벌 수 있는 돈의 양을 리턴하게 된다.

 

각각의 경우 상담을 하거나 / 하지 않거나의 두가지 선택지가 있는데,

 

상담을 할 시, 상담 완료 기간만큼 시간이 지나고, 상담해서 받을 수 있는 금액을 얻게 된다.

상담을 하지 않을 시, 금액을 얻지 못하지만, 곧바로 다음 날 있는 상담을 선택할 지 말지를 결정할 수 있게 된다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T[20], P[20];
int N;
int dfs(int day) { //day번째 날 부터 벌 수 있는 최대 돈
    if (day >= N) return 0;
    int ret = 0;
    if (T[day] + day <= N) {
        ret = max(ret, dfs(day + T[day]) + P[day]);
    }
    if (day + 1 < N)
        ret = max(ret, dfs(day + 1));
    return ret;
}
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> T[i] >> P[i];
    }
    cout << dfs(0) << endl;
}