BOJ 14501 - 퇴사 / C++

문제 링크 : https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

 

 

풀이

문제의 형태 덕분에 DP로 풀이해야한다는 것은 쉽게 감이 오지만 점화식을 세우기는 어렵다.

먼저 i일에 할 수 있는 행동을 생각해보면

1. Ti 만큼의 날짜를 소요하여 Pi를 획득한다.

2. 그냥 i+1로 건너뛴다.

 

1번 경우에는 DP[i + Ti] + P[i] = DP[i]가 될 것이고

2번 경우에는 DP[i + 1] = DP[i]이 될 것이다.

 

따라서, DP[i]에 대한 점화식을

DP[i] = max(DP[i + Ti] + P[i], DP[i + 1])로 세울 수 있다.

 

하지만, 이렇게 점화식을 세우려면

DP[i]보다 DP[i + Ti]가 먼저 계산되어있어야 하므로 우리는 거꾸로 생각해볼 수 있다.

 

위의 예시에서 살펴보면

7일에는 소요시간이 2일이므로 완료 불가능하고

6일에는 소요시간이 4일이므로 완료 불가능하고

 

5일에는 소요시간이 2일이므로 완료 가능하다.

따라서 건너뛰는 경우인 DP[i+1]와 시간을 소요하여 7일로 이동하는 DP[i + Ti] + P[i]중 큰 값을 선택한다.

이 경우에 DP[i+1]은 0이고 DP[i + Ti] + P[i]는 15이므로 후자를 선택한다.

 

4일에는 소요시간이 1일이므로 완료 가능하다.

따라서, 앞선 경우와 같이 DP[i+1]과 DP[i + Ti] + P[i]중 큰 값을 선택하는데

Ti = 1이므로 당연히 후자를 선택하고 15 + 20 = 35의 값을 가진다.

 

이렇게 1일까지 탐색을 마치고나면 DP[1]에는 가질 수 있는 최댓값이 존재하므로

DP[1]을 정답으로 출력해주면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int DP[16] = { 0, };
pair<int, int> v[16] = { {0, 0}, };

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;

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

    for(int i=n; i>0; i--){
        if(i + v[i].first > n+1) DP[i] = DP[i+1];
        else DP[i] = max(DP[i+1], DP[i + v[i].first] + v[i].second);
    }

    cout << DP[1];
}

📎위의 테스트 케이스에서 DP[n] ~ DP[1] 출력

0
0
15
35
45
45
45