퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

#include <iostream>
using namespace std;
 
int t[21];
int p[21];
int n;
int ans = 0;
void go(int day, int sum) {
    if (day == n + 1) {
        if (ans < sum) ans = sum;
        return;
    }
    if (day > n + 1) {
        return;
    }
    go(day + 1, sum);
    go(day + t[day], sum + p[day]);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) 
    {
        cin >> t[i] >> p[i];
    }
    go(1, 0);
    cout << ans << '\n';
    return 0;
}

DP 버전

뒤에서 부터 앞으로도 가능하다!!

#include <iostream>
#include <algorithm>
 
int t[20];
int p[20];
int d[20];
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        cin >> t[i] >> p[i];
 
 
    // 역순으로 dp
    for (int i = n; i >= 1; i--)
    {
        if (i + t[i] <= n + 1)
        {
            d[i] = max(d[i + 1], d[i + t[i]] + p[i]);
        }
        else
            // 고르지 않은 것
            d[i] = d[i + 1];
    }
 
    cout << d[1] << '\n';
}