14501 퇴사

되게 전형적인 DP문제인데 난 DP에 약해서 시간이 걸렸다
다른사람 코드도 좀 참고함

문제 링크

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

풀이

그날 상담을 하거나 하지 않거나 두 가지 경우가 존재한다.
두 경우 모두를 고려하여 해당 날짜의 max cost값이 들어가게 DP를 해주면 된다.
N+1번째 날에는 항상 최대 수익이 들어가게 되므로 마지막에 N+1번째 날의 cost를 출력하도록 하였다.

C++ 코드

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int T[16] = {0};
int P[16] = {0};
int cost[16] = {0};
int ans;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>N;
    
    for(int i=1; i<=N; i++){
        cin>>T[i]>>P[i];
    }
    
    for(int i=1; i<=N; i++){
        if(i+T[i]-1<=N){
            cost[i+T[i]] = max(cost[i+T[i]], cost[i] + P[i]);
        }
        cost[i+1] = max(cost[i], cost[i+1]);
    }
    
    cout<<cost[N+1]<<endl;
    
    return 0;
}