백준 15486 퇴사 2(c++)

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

15486번: 퇴사 2

이 문제는 예전에 풀기도 했었고, 보자마자 DP가 떠올랐습니다. 상담으로 얻을 수 있는 최대 수익을 출력해야 하는데, 이전에 벌어들인 수익을 누적시켜야 하기 때문에 DP를 이용했습니다. 

기본 로직은 상담을 하는 것과 하지 않는 것으로 나누고,

상담을 했을 때는 max(상담을 했을 때의 누적값, 그날 상담으로 얻을 수 있는 비용)이고,

상담을 하지 않은 경우에는 max(그 날 상담으로 얻을 수 있는 비용, 다음 날 상담으로 얻을 수 있는 비용)입니다.

 

<코드>

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int d[1500001];
    int t[1500001];
    int p[1500001];
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> t[i] >> p[i];
    }
    for (int i = 0; i < n; i++)
    {
        d[i + t[i]] = max(d[i + t[i]], d[i] + p[i]);
        // 상담 O
        d[i + 1] = max(d[i + 1], d[i]);
        // 상담 X
    }
    cout << d[n] << '\n