[백준] 14501번 퇴사 (C++) - dynamic programming

문제

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

14501번: 퇴사

코드

#include <iostream>

using namespace std;

int dp[16];
int t[16];
int p[16];

int main(){
  int n;
  cin >> n;

  for(int i=1; i<=n; i++){
    cin >> t[i] >> p[i];
  }

  for(int i=n; i>=1; i--){
    if(t[i]+i-1 > n){
      dp[i] = dp[i+1];
    }else{
      dp[i] = max(dp[i+1], dp[i+t[i]]+p[i]);
    }
  }

  cout << dp[1];

  return 0;
}

정리

이제 dp문제 좀 익숙해진다 싶었는데 어림도 없었다.

나한테는 정말 어려운 문제였다.

 

이 문제는 dp를 반대로 보면 문제가 풀기 쉽다.

'첫째날 → 마지막날'로 보는 것이아니라 '마지막날 → 첫째날'로 보면 편하다.

 

다음 표를 예시로 봐보자

7일 - 잡혀있는 상담기간이 2일이므로 상담을 진행할 수 없다. → 최대이익 0

 

6일 - 잡혀있는 상담기간이 4일이므로 상담을 진행할 수 없다. → 최대이익 0

 

5일 - 잡혀있는 상담기간이 2일이므로 5~6일에 걸쳐 상담을 진행할 수 있다. → 최대이익 15

 

4일 - 잡혀있는 상담기간이 1일이므로 4일에 상담을 진행할 수 있다. → 최대이익 15(5~7일에서의 최대이익)+20 = 35

 

3일 - 잡혀있는 상담기간이 1일이므로 4일에 상담을 진행할 수 있다. → 최대이익 35(4~7일에서의 최대이익)+10 = 45

 

2일 - 잡혀있는 상담기간이 5일이므로 2~6일에 걸쳐 상담을 진행할 수 있다. → 지금까지 구해온 최대이익과 2일째 상담을 한 경우의 최대이익을 비교해야 한다. 2일째 상담을 한 경우의 최대이익은 20이므로 최대이익 = 45 (45>20)

 

1일 - 잡혀있는 상담기간이 3일이므로 1~3일에 걸쳐 상담을 진행할 수 있다. → 지금까지 구해온 최대이익과 1일째 상담을 한 경우의 최대이익을 비교해야 한다. 1일째 상담을 한 경우의 최대이익은 35(4~7일에서의 최대이익)+10(1~3일에 걸쳐서 상담을 한 후에 얻은 이익) = 45이다. 지금까지 구해온 최대이익과 동일하므로 최대이익 = 45

 

비교할 때 점화식을 구해보면 밑처럼 나타낼 수 있다.

dp[i] = max(dp[i+1], dp[i+t[i]]+p[i]);

 

dp[i+1] → 지금까지 구해온 최대이익

dp[i+t[i]]+p[i] → i+t[i]일~마지막날에서의 최대이익 + 첫째날~i+t[i]-1일에 걸쳐서 상담을 한 후에 얻은 이익

참조

https://sw-ko.tistory.com/158

https://dinist.tistory.com/30