[백준알고리즘] 15486번 퇴사2

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

옛날에 풀었던 문제를 다시 복기하며 풀어봤다!

아주그냥 바로 풀려서 기분이 좋음^^*

퇴사2 문제는 N이 1500000까지 주어진다는 조건에서 다이나믹 프로그래밍으로 풀어야한다는 것을 바로 알 수 있다!

내가 문제를 푼 방법은 이러하다!

< dp 배열 (최대 수익 배열) 을 뒤에서부터 채워나간다! >

::채워나가는 조건::

1) 상담이 퇴사 날짜 후에 끝나는 경우의 최대 수익을 고려한다.

현재 날짜에서부터 상담이 끝나는 날짜를 확인하여 퇴사 날짜 이후에 끝나는 상담은 할 수 없으므로,

그 상담을 하지 않은 다음 날짜의 최대 수익이 현재 날짜의 최대 수익이 된다.

if (i + T[i] > N + 1){

dp[i] = dp[i + 1]; }

2) 상담이 퇴사 날짜 전에 끝나는 경우의 최대 수익을 고려한다.

==> 이 상담을 할 경우와 이 상담을 하지 않을 경우 두 가지를 고려한다.

이 상담을 할 경우 => 현재 상담의 수익과 상담이 끝났을 때의 날짜의 최대 수익을 합한 것이 현재 날짜의 수익이다. => P[i]+dp[i+T[i]]

이 상담을 하지 않을 경우 => 그 다음 날짜의 최대 수익이 현재 날짜의 수익이다. => dp[i+1]

이 두가지 경우 중 더 큰 값이 현재 날짜의 최대 수익이 된다.

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

그림설명!

나의 코드!

#include<iostream>
using namespace std;
#define max(a, b) (a > b ? a : b)
 
int T[1500002];
int P[1500002];
int dp[1500002];
 
int main(void)
{
    int N, i;
    cin >> N;
 
    for (i = 1; i <= N; i++)
    {
        cin >> T[i] >> P[i];
    }
 
    for (i = N; i >= 1; i--)
    {
        // i+T[i] 가 N+1을 넘어가면 그 앞의 값 그대로.
        if (i + T[i] > N + 1)
        {
            dp[i] = dp[i + 1];
        }
        else
        {
            dp[i] = max(dp[i+1], P[i]+dp[i+T[i]]);
        }
    }
 
    cout << dp[1];
 
    return 0;
}