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;
}