[C++] 백준 14501번 퇴사

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

풀이

dp(n)을 n일차까지 처리했을 때 받을 수 있는 최대 금액이라고 정의하자.

1일차부터 시작하여, 해당 일자에 상담을 수행한다면 얻게 될 이익을 계산한다.
만약 기존 dp(n)보다 새로 계산한 n일차의 이익이 크다면, dp(n)을 갱신한다.
그렇지 않으면 dp(n)은 기존의 값을 유지한다.

코드

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

typedef pair<int, int> pi;

int main()
{
    int n, t, p;
    vector<pi> v;
    vector<int> dp;
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> t >> p;
        v.push_back({t, p});
    }
    
    dp.assign(n+1, 0);
    for(int i=0; i<n; i++){
        for(int j=i+v[i].first; j<=n; j++){
            if(dp[j] < dp[i] + v[i].second){
                dp[j] = dp[i] + v[i].second;
            }
        }
    }
    
    cout << dp[n];
    
    return 0;
}