백준 15486번 퇴사 2

🔒[문제 url]

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

🔑알고리즘

선택지는 다음과같이 존재한다.
1. 상담이 끝나는 시점이 $N$일을 초과하여 상담하지 못 하는 경우
dp[i] = dp[i + 1]
2. 상담이 끝나는 시점이 $N$일을 이하이나, 상담하지 않는 경우 dp[i] = dp[i + 1]
3. 상담이 끝나는 시점이 $N$일을 이하여서 상담하는 경우
dp[i] = dp[i + T[i]] + P[i]

• 즉 점화식은, 상담이 끝나는 시점이 $N$일 이하일 경우

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

가 된다. 따라서 뒤에서부터 순회하며 최대 수익을 갱신하고, dp[0]의 값이 최종 답안이 된다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <algorithm>
using namespace std;

int n;
int T[1'500'000], P[1'500'000];
int dp[1'500'001]{ 0, };

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> T[i] >> P[i];
}



void SOLVE()
{
    for (int i = n - 1; i >= 0; i--)
    {
        // If Time over N, then take next day's dp
        if (i + T[i] > n)
        {
            dp[i] = dp[i + 1];
            continue;
        }

        // Recurrence relation
        else dp[i] = max(dp[i + 1], dp[i + T[i]] + P[i]);

    }
    cout << dp[0];
}


int main()
{
    INPUT();

    SOLVE();
}

🥇문제 후기

DP는 역시... 아이디어만 잡으면 10줄 내외인데...... 왜..........
그런데 왜...................얄미운 DP....
그래도 이 문제는 쉽게 풀었으니 일단 만족...
그건 그렇고 포스팅이 밀리기 시작했다. 어쩌면 좋아?