[백준/C++][퇴사2(15486번)]

문제

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

15486번: 퇴사 2

문제 풀이

일단 크게 두가지 경우로 나뉜다.

 

1. 시간이 초과되서 상담을 그날 상담을 못하는 경우

2. 시간이 초과되지 않아서 그날에 상담을 할 수 있는 경우

 

일단 1번의 경우이다.

상담을 한다면 N보다 초과되어서 이날의 상담은 하지 못하므로 이날의 최대 dp의 값은 i+1의 값이 된다. -> 이날 상담을 안하고 다음 날 한다.

 

2번의 경우

1.상담을 할 수 있으므로 상담을 하는 경우

2.상담을 안하는 경우

이렇게 또 2가지 경우로 나뉜다.

1번 경우는 상담을 하고 그날의 상담일당 + i+T날의 dp값이 1번의 값이다. -> dp[i+T]값은 그날의 최선의 값이기 때문에 가능.

2번의 경우는 상담을 안함으로 dp[i+1]이 값이 된다.

dp[i] = max(dp[i+1],dp[i+T]+v[i].second) 라는 점화식을 얻을 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
int N;
int main(void){
    int dp[1500001],result = -1;
    vector<pair<int,int>> v;
    v.push_back({0,0});
    cin >> N;
    for(int i = 0;i<N;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        dp[i+1] = 0;
        v.push_back({a,b}); //시간,가치
    }
    for(int i = N;i>=0;i--){
        int T = v[i].first;
        if(i+T>N+1){
            dp[i] = dp[i+1];
            result = max(result,dp[i]);
        }
        else{
            dp[i] = max(dp[i+1],v[i].second+dp[i+T]);
            result = max(result,dp[i]);
        }
    }
    cout << result;
}