[Gold 5] 15486 퇴사 2

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

15486번: 퇴사 2

 

이 문제는 dynamic programming 문제이다.

dp에 상담 금액의 최대 값을 저장한다.

이때 상담 시간을 결정하면 일정 기간동안 다음 상담을 신청할 수 없다는 조건이 있기 때문에 현재 결정한 상담 시 금액과 지난 상담의 합과 dp에 저장된 현재 결정한 상담 시간과의 최대 값을 골라 dp에 저장해야한다.

 

#include<iostream>
using namespace std;

int N;
pair<int,int> arr[1500001];
int dp[1500001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
    cin>>N;
    for(int i = 1;i<=N;i++)
        cin>>arr[i].first>>arr[i].second;
    
    int result = 0;
    for(int i = 1;i<=N+1;i++){
        result = max(result, dp[i]);
        dp[i+arr[i].first] = max(result + arr[i].second, dp[i + arr[i].first]);
    }

    cout<<result<<'\n';
    return 0;
}