백준 14501번 퇴사

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

이 문제는 혼자 힘으로 하려다가.. 결국 다른사람의 코드를 보고 이해하였다. 아래가 참조한 블로그이다.

http://jongnan.tistory.com/9

풀이

1. N번째 날에 가질 수 있는 최대 금액 d[N] 을 구해야 한다.

2. N번째 날에 선택할 수 있는 경우는 2가지이다.

   - N번째날 상담을 한다 

     -> N번째 날 금액(P)을 받고, T일이 지난 후에 다시 상담여부 결정 ( find(day + T[day]) + P[day] )

   - N번째날 상담을 하지 않는다.

     -> 다음 날부터 다시 상담여부를 결정 ( find(day + 1) )

3. 딱 N번째 날에 끝난다면

    - 0을 반환 ( day == N + 1 )

    N번째 날을 초과한다면

    - 매우 큰 - 값을 반환하여 선택되지 않도록 한다. ( day > N + 1 )

    메모이제이션을 통해 N번째 날의 최대금액을 이미 구했다면 반환

    - 이는 어차피 max 를 구하는 부분에서 여러 경우 중 큰 값을 택할 것이므로 다시 계산하지 않아도 되기 때문이다.

4. 2, 3번 알고리즘을 재귀로 반복하며 최대 금액을 구하면, 마지막 날에서 최대금액을 얻을 수 있다.

#include <iostream>
#define MAX 15
using namespace std;
int N;
int T[MAX + 1] = {0, };
int P[MAX + 1] = {0, };
int d[MAX + 2] = {0, };
int find(int day) {
    if (day == N + 1) {
        return 0;
    }
    if (day > N + 1) {
        return (-1 * 987654321);
    }
    if (d[day] > 0) {
        return d[day];
    }
    
    return d[day] = max(find(day + 1), find(day + T[day]) + P[day]);
}
int main()
{
    scanf("%d", &N);
    
    for (int i = 1; i <= N; ++i) {
        scanf("%d %d", &T[i], &P[i]);
    }
    printf("%d\n", find(1));
    
    return 0;
}