[SW역량] 14501. 퇴사

 

N수가 작아서, 완전탐색으로 풀어도되고,

그렇지 않고 가능하다면 DP로 풀어도 되는 문제이다.

여러가지 DP 해법을 보다가, 가장 와 닿는 풀이방법을 찾았다.

d[i] : i일로부터 N일까지 최대 수익

이라고 정하면, 식을 자연스럽게 세울 수 있다.

 

d[i] = max(d[i+1], d[i + t[i]] + p[i])

이제 d[i]를 solve(int i)라고 놓고, 리턴값을 d[i]으로 설정해서 풀어보자.

그렇다 Top-down 방식의 동적계획법이다.

기저 조건은,

d[N + 1] = 0

d[N + 1 초과] = - INF

라는 것이다. 

이것은 예제 하나를잡아 하나하나 대입해가면서, 마지막 조건을 생각하면 이해가 쉬운 편이다.

Hint:

마지막 날의 t[i]가 1이라면, d[i + t[i]] + p[i] 값이 나오는 것을 허락해야 한다. 즉, d[i+1]은 0으로 잡아야 한다.

하지만, i가 그 이상을 초과한다면 수익을 계산할 수 없으므로, max와 비교해주었을 때 무조건 뽑히지 않아야 한다.

즉, -INF 값을 가져야 한다.

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::max;
const int INF = 987654321;
int N;
int t[15], p[15], d[21];

int solve(int k){
    if (k == N) return 0;
    if (k > N) return -INF;
    int& ret = d[k];
    if (ret != -1) return ret;

    return ret = max(solve(k + 1), solve(k + t[k]) + p[k]);
}

int main() {
    scanf("%d", &N);
    for (int i=0; i<N; ++i){
        scanf("%d %d", &t[i], &p[i]);
    }
    memset(d, -1, sizeof(d));
    printf("%d\n", solve(0));
    return 0;
}