BOJ)14501 퇴사

문제: icpc.me/14501

i일 부터 일을 할 때 얻을 수 있는 급여의 최댓값으로 DP테이블을 잡으면 쉽게 계산할 수 있는 문제이다.

dp[i]의 점화식은 max(dp[i+1],dp[i+t[i])+p[i]) 가 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, dp[16], t[16], p[16];
int func(int pos) {
    if (pos == n + 1)return 0;
    if (pos > n + 1)return -987654321;
    int &ret = dp[pos];
    if (ret != -1)return ret;
    return ret = max(func(pos + 1), func(pos + t[pos]) + p[pos]);
}
int main() {
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= n; i++) 
        scanf("%d%d", &t[i], &p[i]);
    printf("%d\n", func(1));
    return 0;
}