퇴사 (백준 14051번)

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

14501번: 퇴사

 

이 문제는 동적 계획법을 통해서 해결할 수 있다. 

 

dp 테이블에는 x일에 얻을 수 있는 최대 수익이 들어간다. 그래서 x일이 되었을 때, 해당 상담을 진행할 지, 안 할지 선택해서 dp 테이블에 값을 넣어준다.

 

상담을 할지 안 할지는 두 값중 더 큰 이익으로 정한다.

 

1. x번째 일을 했을 때 수익(= x일 수익 + 상담에 소요되는 시간 뒤 날짜 최대 수익)
   • 즉 p[x] + dp[x + t[x]] , 해당 날짜에 상담을 하면 소요되는 시간 날짜부터 일 을 할 수 있기 때문 
2. x 번째 일을 안 했을 시 수익, 일을 안 하기에 다음 날짜에서 얻을 수 있는 최대 수익을 그대로 가져오면 된다. 
   • dp[x + 1]

 

그리고 x일에서 해당 상담을 진행하는데 걸리는 시간을 더한 결과는 n보다 작거나 같아야한다. 그래야만 상담 중간에 퇴사일이 되는것을 막을 수있다. 따라서 x + t[x] <= n으로 나타낼 수 있다.

 

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

import sys

n = int(sys.stdin.readline())
t_list = [0 for i in range(n+1)]
p_list = [0 for i in range(n+1)]

dp = [0 for _ in range(n+1)]
for i in range(n):
    t, p = map(int, sys.stdin.readline().split())
    t_list[i] = t
    p_list[i] = p

for i in range(n-1, -1, -1):
    if t_list[i]+i <= n:       
        dp[i] = max(p_list[i] + dp[i + t_list[i]], dp[i+1])   
    else:                 
        dp[i] = dp[i+1]
print(dp[0])