백준 14501. 퇴사 (DP)

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

14501번: 퇴사

이문제 못풀어서 다음 블로그에서 풀이법을 가져왔다. 

https://velog.io/@sj-lee33/%EB%B0%B1%EC%A4%80-14501%EB%B2%88-%ED%87%B4%EC%82%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-c-%ED%92%80%EC%9D%B4

백준 14501번 : 퇴사 (알고리즘 c++ 풀이)

동적 프로그래밍을 이용하는 문제이다. 

문제를 역순으로 생각하면 쉽게 풀 수 있다. 

7일: 2일 걸림, 0일 남음, 진행 x

6일: 4일 걸림, 1일 남음, 진행 x

5일: 2일 걸림, 2일 남음 ,진행 가능, 15

4일: 1일 걸림, 3일 남음, 진행 가능, 15 + 20

3일: 1일 걸림, 4일 남음, 진행 가능, 15 + 20 + 10

2일: 5일 걸림, 5일 남음, 진행가능: 20 or 45

1일: 3일 걸림, 6일 남음,진행 가능

if 1일차 진행하면 10(1) + 20(4) + 15(5)

elif 1일차 진행안하면 10(3) + 20(4) + 15(5) 똑같음

 

이를 코드로 옮기면 다음과 같다. 

#include <iostream>
#include <string>

using namespace std;

int n;
pair<int, int> arr[17];
int d[17]; 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);


    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i].first >> arr[i].second;
    }


    for(int i = n; i > 0; i--)
    {
        int deadline = i + arr[i].first;
        if(deadline<=n+1) d[i] = max(d[i+1], d[deadline]+arr[i].second);
        else d[i] = d[i+1];
    }
    
    cout << d[1];

    
    
}