백준 14501 파이썬 퇴사

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

14501번: 퇴사

 

 

이 문제를 풀 때 핵심적인 아이디어는, 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 다이나믹 프로그래밍 알고리즘을 수행해야 한다는 것이다 !

문제에서 주어진 예시 N = 7 인 경우에는 6일과 7일자의 상담을 수행하면 7을 넘기게 된다. 이와 같은 경우를 고려하기 위해서 뒤에서부터 DP를 수행하여 저장한다. 

경우를 나누는 것은 두가지로, i번째 날의 상담을 수행했을 때 n을 넘는다면 이 경우는 불가능하니까 value를 0이라고 생각하여 dp 그래프에 0 값으로 처리를 한다.

dp[i] = dp[i+1] # 단, 여기서 dp list의 맨 마지막 인덱스에 0을 삽입해주어야 한다 ! 

그리고 상담을 수행해도 n보다 작거나 같은 경우에, dp[i] 번째 날부터 마지막 날까지 낼 수 있는 최대 이익을 비교하여 구한다.

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

 

n = int(input())
t = []
p = []
dp = []

for i in range(n):
    a, b = map(int, input().split()) # 소요 일수, 얻는 비용
    t.append(a)
    p.append(b)
    dp.append(b) # 비용 최대를 구해야하니까 dp는 비용 중심이다 !
dp.append(0)

for i in range(n-1, -1, -1): # (n-1) ... 0
    if t[i] + i > n: # 상담 불가능한 경우
        dp[i] = dp[i+1] 
    else: # 상담 가능한 경우 지금 건수를 할지말지
        dp[i] = max(dp[i+1], p[i] + dp[i + t[i]]) 
print(dp[0])