[python] 백준 14501번: 퇴사

 

문제

www.acmicpc.net/problem/14501

14501번: 퇴사

 

---

분류

다이나믹 프로그래밍

 

아이디어

날짜를 index로 삼아 (1일째 = dp[1]...) 해당 일까지 얻을 수 있는 금액의 최대 이윤을 저장한다.

bottom-up 방식으로, 최대 이윤을 구할 수 있는 N일부터 dp[i] 를 계산한다.

점화식은

dp[i] = max(dp[i]+dp[time[i]+i] , max_pay) 다.

 

max_pay 는 해당일까지 계산한 최대이윤 값이다. 만약 N=7 기준으로,

7일차에 일할 경우 받는 pay = 50, 걸리는 시간 = 1이면 

dp[7] = 50 이다. max_pay 또한 0에서 50 이 된다.

 

6일차에 일을 할 수 없는 경우(즉,6일차 일이 걸리는 시간과 현재 시간합이 n+1 이상을 의미)

dp[6] = 50 이다. 왜냐 하면, 6일에 일을 안하고 7일에 일을 하면 되기 때문.

(이 부분을 생각하지못해 틀렸었다)

max_pay = 50 이 유지된다.

 

5일차 까지의 최대 이윤 = 40, 걸리는 시간 = 3 이면

5일차에 일을 할 경우 6일,7일에는 당연히 일을 할 수 없다.

5일차의 dp 값은 40이 아니라 50이 되어야 한다.

왜냐면 5일차에 일을 하게 돼 얻게되는 이윤보다 기존의 경우의 최대 이윤이 크기 때문.

그리고 기존의 최대 이윤의 경우(max_pay를 얻게되는 경우)는 7일차에 일을 하는 경우이고 이는 5일차에 일을 하지 않고 7일차에 달성할 수 있기 때문에 예외는 없을 것이다.

 

말하자면 생각의 함정이 될 수 있는 부분은 

"꼭 모든 스케줄이 꽉차게 구성되어야만 최대 이윤을 얻는다." 인 것이다.

 

나도 저렇게 생각했지만 실상은 하루나 며칠을 쉬더라도 최대 이윤을 달성할 수 있기 때문에

최대 이윤과의 계속적인 비교로 dp 값을 갱신해야 한다.

 

dp 배열의 의미 자체가 "그 날까지 일을 했을 때의 최대 이윤이 담긴 배열" 인 것이다.

 

코드

 

from sys import stdin
n = int(input())
times = [0]
pays = [0]
for i in range(n):
    t, p = map(int, stdin.readline().split())
    times.append(t)
   pays.append(p)
 
dp = [0] * (n+2)
max_pay = 0
for i in range(n,0,-1):
    if i + times[i] > n+1:
        dp[i] = max_pay
    else:
        if i+times[i] == n+1:
            dp[i] = max(pays[i],max_pay)
        else:
            dp[i] = max(pays[i] + dp[times[i] + i],max_pay)
    max_pay = max(max_pay,dp[i])
 
print(max_pay)