[백준] 15486번*

💻 C++ 기반

퇴사 2
https://www.acmicpc.net/problem/15486

1. 테이블 정의하기
   dp[i] : i번째날에 상담을 시작했을 때 얻을 수 있는 최대 이익
2. 점화식 찾기

• dp[N]부터 채워주기 (반복문을 i=N부터 시작)
• 만약 i번째날에 상담을 시작할 수 있다면, dp[i+1]의 값과(상담을 시작하지 않았을 경우) 상담이 끝나는 다음 날의 dp값에 i번째날에 상담을 시작하면 얻을 수 있는 이익을 더한 값을(상담을 시작했을 경우) 비교해서 최댓값을 가져옴
• 만약 i번째날에 상담을 시작할 수 없다면, dp[i+1]의 값을 그대로 가져옴

3. 초기값 정하기
   dp[N + 1] = 0

#include <cstdio>
#include <utility>
#include <algorithm>

#define MAX_N 1500002

using namespace std;

int dp[MAX_N];
pair<int, int> schedule[MAX_N];

int main()
{
    int N;
    scanf("%d", &N);

    for (int i = 1; i <= N; i++)
    {
        int T, P;
        scanf("%d %d", &T, &P);
        schedule[i].first = T;
        schedule[i].second = P;
    }
    
    for (int i = N; i >= 1; i--)
    {
        if (i + schedule[i].first - 1 <= N)
        {
            dp[i] = max(dp[i + 1], dp[i + schedule[i].first] + schedule[i].second);
        }
        else
        {
            dp[i] = dp[i + 1];
        }
    }
    
    printf("%d", *max_element(dp + 1, dp + N + 1)); // 사실상 dp[1]을 출력해도 됨
    return 0;
}