N이 15 이하로 작기 때문에 전체 가지수를 전부 탐색하였다.
1. 마지막 return시 조건 제대로 설계하기
2. 가지치기 할때, 끝에날짜 조심하기(퇴사기준)
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int N;
int result[20];
int dab;
struct Dday{
int time;
int cost;
};
Dday sch[20];
int sum;
void dfs(int level, int now,int sum) {
if (now >= N) {
//최대이익 찾기
if (dab < sum) dab = sum;
return;
}
for (int i = now; i < N; i++) { //끝에 날짜 주의해야함!!
if (i + sch[i].time > N) {
sch[i].cost = 0;
}
result[level] = sch[i].cost;
dfs(level + 1, i + sch[i].time,sum+result[level]);
}
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> sch[i].time >> sch[i].cost;
}
dfs(0, 0,0);
cout << dab;
return 0;
}