[C++] 백준/Gold/15486. 퇴사 2

문제: 퇴사 2 (백준 15486번)

문제 분석

• 입력: $N$일 동안 상담을 진행할 수 있으며,
  각 상담은 걸리는 기간 $T_i$와 얻을 수 있는 금액 $P_i$를 가진다.
• 목표: 상담을 적절히 선택하여 얻을 수 있는 최대 수익을 계산하는 문제.
• 조건: 상담이 끝나는 날을 초과하면 진행할 수 없다.

---

해결 방법: 동적 계획법 (DP)

이 문제는 배낭 문제 (Knapsack Problem)와 유사하다.
각 날짜별로 상담을 선택할지 말지를 결정해야 하며, 최적의 선택을 누적하면서 해결해야 한다.

DP 테이블 정의

• dp[i]: i번째 날까지 얻을 수 있는 최대 수익
  • 즉, i일이 끝났을 때 가능한 최대 이익을 저장한다.

점화식

1. 현재까지의 최대 수익 유지
   
   $$dp[i]=max(dp[i],dp[i-1])$$
   
   
   • i번째 날까지의 최대 수익은 이전 날까지의 최대 수익과 비교하여 갱신된다.
   • 즉, 오늘 상담을 하지 않더라도 이전 날까지의 최대 수익은 유지되어야 한다.
2. i일에 상담을 선택하는 경우
   • 상담을 하면 $T_i$일 후(즉, $i+T_i$)에 보상이 지급되므로,
     $$dp[i+T_i]=max(dp[i+T_i],dp[i]+P_i)$$
   • $i+T_i$가 $N$을 초과하면 상담을 할 수 없다.

---

코드 설명

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    vector<pair<int, int>> v(n);
    vector<int> dp(n + 1);

    // 상담 일정 입력
    for (int i = 0; i < n; i++)
    {
        cin >> v[i].first >> v[i].second;  // {T_i, P_i}
    }

    // DP 수행
    for (int i = 0; i < n; i++)
    {
        // i일까지의 최대 수익 유지
        if (i > 0) dp[i] = max(dp[i], dp[i - 1]);

        int index = i + v[i].first;  // 상담이 끝나는 날짜
        if (index <= n)  // 퇴사일을 넘지 않으면 상담 가능
        {
            dp[index] = max(dp[index], dp[i] + v[i].second);
        }
    }

    // 최댓값 출력
    cout << *max_element(dp.begin(), dp.end());
}