퇴사

#include<iostream> #include<fstream> #include<vector> #include<list> #include<algorithm> #include<cmath> using namespace std; int days; int work[100]; int pay[100]; int max = 0; int f(int d, int sum) { if (d > days + 1) { return 0; } else if (d == days +1 ) { return sum; } return std::max(f(d + 1, sum), f(d + work[d], sum + pay[d])); } int main() { ifstream in("in.txt"); in >> days; for (int t = 1; t <= days; t++) { in >> work[t] >> pay[t]; } cout << f(1, 0) << endl; } 

DFS로 풀이

오늘 일한다면 다음 작업은 시작은 day+걸리는 시간, 금액은 여태까지 벌은 금액 + 오늘 벌 금액

오늘 일을 안한다면 다음 작업 시작은 day +1일, 금액은 동일

퇴사 날짜를 넘긴다면 금액을 0으로 만들어 무효처리

퇴사 날짜에 도착하면 여태까지의 금액 returm

최종적으로 DFS를 통한 max값 출력