[BOJ 14501] 퇴사

이 문제는 상담할 수 있는 N일이 주어지고 상담을 마치는데 걸리는 시간과 상담을 했을 때 얻는 수익이 주어진다. N+1일날 퇴사를 하고자 할때 남은 N일 동안 상담을 진행하여 낼 수 있는 최대 수익을 구하는 문제다.

문제 풀이 : 각 날에 상담을 한다 / 안 한다로 구분하여 모든 경우의 수를 탐색해 최대 수익을 계산했다.

 

#include <iostream>
#include <vector>
using namespace std;
 
int N;
int ans;
 
void solve(vector <pair <int, int> > &v, int day, int pay) {
    if (day > N) {
        return;
    }
 
    if (day==N) {
        if (ans < pay) ans = pay;
        return;
    }
 
    solve(v, day + v[day].first, pay+v[day].second);
    solve(v, day + 1, pay);
}
int main() {
    cin >> N;
    vector <pair<int, int> > v(N);
 
    ans = 0;
    for (int i = 0; i < N; i++) {
        int T; int P;
        cin >> T >> P;
        v[i].first = T;
        v[i].second = P;
    }
 
    solve(v,0,0);
 
    cout << ans << '\n';
 
    return 0;
 
}