백준 퇴사2(c++)

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

15486번: 퇴사 2

dp[i]를 i일 바로 전까지 일해서 얻을수 있는 최댓값이라 하면 

1) i-1일까지 일해서 얻는 비용

2) i-1일에는 일 안하지만  그 이전에 어느 구간에 일한 구간 

이 두가지 경우 중에 더 큰값을 dp[i]에 넣어주어야 한다. 

 

어렵다..

#include<iostream>
#include<vector> 
#include<cmath>

using namespace std;

vector<pair<int,int>>arr;
vector<int>dp;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N; 
    arr.assign(N + 1, { 0,0 });
    dp.assign(N + 2, 0);

    int t, p;
    for (int i = 1; i <= N; i++) {
        cin >> t >> p;
        arr[i] = { t,p };
    }
    int ans = 0;
    for (int i = 1; i <= N+1; i++) {
        if (ans < dp[i])ans = dp[i];
        if (i + arr[i].first > N + 1)continue;
        //
        dp[i + arr[i].first] = max(dp[i + arr[i].first],ans + arr[i].second);
    }

    cout << ans;



    return 0;
}