퇴사
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int N;
cin>>N;
vector <vector<pair<int,int>>> vec(N+1);
vector<int> dp(N+1);
int t,p;
for(int i=1;i<=N;i++){
cin>>t>>p;
if (i + t - 1 <= N) vec[i+t-1].push_back(make_pair(i,p));
}
for(int i=1;i<=N;i++){
dp[i]=dp[i-1];
for(pair<int,int> p : vec[i]){
dp[i]=max(dp[i],dp[p.first-1]+p.second);
}
}
cout<<dp[N];
return 0;
}
if (i + t - 1 <= N)
이거 추가 안하고서 왜 코드 안돌아가징.. 이랬다..
- dp 식에서
dp[p.first-1]+p.second
인데 처음엔 dp[p.first]+p.second
로 작성했다,,
- 식: 현재 i일에서 끝나는 모든 상담에 대해 진행
start: 현재 보고있는 상담이 시작하는 날 / p: 현재 보고있는 상담의 금액
dp[i]=max(dp[i-1]+dp[start-1]+p)