백준 14501 퇴사

앞선 문제들을 풀었다면 쉽게 풀 수 있는 문제이다.

마찬가지로 현재 날짜를 선택하는 경우와 선택하지 않는 경우로 나눠서 풀면된다.

N+1일을 넘어가지 않도록 하는 것이 중요하다.(딱 N+1일에 끝나도록 한다.)

 

답이 될 수 있는 경우에 return을 하는 것을 매번 까먹는다.

까먹지 않도록 주의

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n;
int ans;
 
void solve(int idx, int sum, vector<int> t, vector<int> p) {
    //N+1일을 넘어가면 안되므로 return
    if (idx > n)return;
    //N+1일이면 max값과 비교한다.
    if (idx == n) {
        ans = max(ans, sum);
        //return하는거 까먹지 말자 맨날 까먹는다..
        return;
    }
    //N+1일에 도달하지 않았으면 계속 진행
    //현재 날짜를 선택한다.
    solve(idx + t[idx], sum + p[idx], t, p);
    //현재 날짜를 선택하지 않으면 다음 날로 간다.
    solve(idx + 1, sum, t, p);
}
 
int main(int argc, char** argv) {
    cin >> n;
 
    vector<int> t(n);
    vector<int> p(n);
 
    for (int i = 0; i < n; i++) {
        cin >> t[i] >> p[i];
    }
 
    solve(0, 0, t, p);
 
    printf("%d\n", ans);
 
    return 0;
}