백준 14501 - 퇴사

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

 

 

풀이과정

 

DP를 통해 점화식을 구하되, N+1일째를 초과하는지 확인 후 거꾸로 저장해야 한다. 

 

점화식을 아래와 같이 정의할 수있다.

dp[day] = max(dp[day+1], dp[day + T[day]] + P[day])

 

1. 여기서 dp[day]란 day에서 시작해서 퇴사일까지 얻을 수 있는 최대값을 의미한다.

즉, dp[0] 는 0일부터 퇴사일까지의 최대값을 의미한다. (1일이 아닌 0일부터 시작한다고 가정한다.)

2. max 조건식 첫번째 값인 dp[day+1] 의 의미는, 아무것도 하지 않고 넘어가는 날 을 의미한다.

예를들어 마지막 두 날짜인 dp[6] 또는 dp[5]는 실행할 수 없으므로

dp[6] = (6+1)날짜부터 최대값,

dp[7] = (7+1)날짜부터 최대값 이 될 것이다. 

 

따라서 데드라인을 설정하고,

if 데드라인을 넘기지 않는다면 점화식을

else 데드라인을 넘긴다면 아무것도 하지 않고 넘어가는 날 을 작성하면 될 것이다.

int deadline = i + t[i];
if(deadline <= N) {
    dp[i] = max(dp[i+1],p[i]+dp[deadline]);
}
else dp[i] = dp[i+1];

 

 

전체 코드

#include <iostream>
#include <vector>
#include <cstring>
#include <stdio.h>
using namespace std;

int main() {
    int N, ans = 0;
    int time,pay;
    int dp[15];
    int t[15];
    int p[15];
    memset(dp,0,sizeof(dp));
    scanf("%d",&N);
    for(int i=0; i<N; i++) {
        scanf("%d %d",&t[i],&p[i]);
    }
    for(int i=N-1; i>=0; i--) {
        int deadline = i + t[i];
        if(deadline <= N) {
            dp[i] = max(dp[i+1],p[i]+dp[deadline]);
        }
        else dp[i] = dp[i+1];
    }
    printf("%d\n",dp[0]);
}