[백준] 14501 퇴사 (C++)

문제

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

풀이

이 문제는 다이나믹 프로그래밍 문제이다.

 

n부터 시작하여 각 상담에 대한 최댓값을 구하는 방법을 사용했다.

 

dp[i] = max (dp[i + 1], dp[ t[i] + i] + v[i]]

 

여기서 상담을 할 수 없는 날이라면, dp[i + 1] 값을 저장한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dp[17] = { 0, };

int main() {
    int n;
    cin >> n;

    vector<int> t(n + 1);
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> v[i];
    }

    for (int i = n; i >= 1; i--) {
        int next = t[i] + i;
        if (next <= n + 1) {
            dp[i] = max(dp[i + 1], dp[next] + v[i]);
        }
        else {
            dp[i] = dp[i + 1];
        }
    }

    cout << dp[1];
    return 0;
}