백준 14501 퇴사 :: 들짐승

<링크>

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

<풀이>

그냥 DFS로 풀어도 된다. i일에 일을 한다, 안한다로 나눠서 최대 2^15만큼의 시간이 걸리기 때문에 상관없다. 불필요한 재귀를 줄여보고자 DP로 풀었다. dp[i] 에는 i일부터 시작해서 벌수있는 최대 수익을 기록했다. 
예를 들어 4일부터 시작해서 벌수있는 최대금액을 dp[4]에 저장해놓으면 나중에 1일에, T1=3이라서 4일로 왔을때나 / 3일에, T3=1이라서 4일로 왔을때 4일부터 시작해서 끝까지 가보는 중복연산을 없앨 수 있다.
i일에서,
1.만약 짤리기 전까지 일을 할수있으면 일한 수익+일끝난 다음날부터 계산한값
2.오늘 일 안하고 내일로 패스하고 계산된값

중 최대값을 dp[i]에 저장하였다.

1은 i+T[i] <= N+1 의 조건을 만족해야하고
2는 무조건 비교해봐야한다.

<소스코드>

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int T[16],int P[16],int dp[16],int N;
int recur(int);
int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i)
        scanf("%d %d", T + i, P + i);
    printf("%d\n",recur(1));
}
int recur(int i)
{
    if (i == N + 1) return 0;
    int &ret = dp[i];
    if (ret != -1)
        return ret;
    int a = 0;
    if (i + T[i] <= N + 1)
        a = max(a, recur(i + T[i]) + P[i]);
    a=max(a,recur(i + 1));
    return ret = a;
}

<피드백>

recur함수에서 기저점 우선순위를 잘못세팅해서 틀렸다고 떴었다.
처음에는

int &ret = dp[i];
if (ret != -1)
    return ret;
if (i == N + 1) return 0;

이런 식으로 해놔서 퇴사 당일까지 왔을 때는 i가 N+1임에도 dp[N+1]에 접근하게 되고 개판이 됐었다.
이런 ㅄ같은 실수를 줄여야 한단계 성장할 수 있을 것 같아서 적었다.