#319 백준 파이썬 [14501] 퇴사

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

 

SOLUTION

다이나믹 프로그래밍을 이용하여 풀이한다.

해법은 뒤에서부터 푸는 것

i번 째 날부터 ~ 마지막 날까지 낼 수 있는 최대 이윤은

1) 현재 일의 이윤 + 현재 일이 필요한 day 뒤의 이윤

2) 현재 일을 하지 않고 넘어갈 때의 이윤 (i+1의 이윤)

1)과 2) 중 큰 값이 현재의 maximum pay가 된다.

 

식으로 표현하자면 다음과 같다.

max_pay[i] = max(pay + max_pay[i + day], max_pay[i+1])

PYTHON CODE

N = int(input())
work_pay = []
max_pay = [0] * N

for _ in range(N):
    work_pay.append(list(map(int, input().split())))
   
for i in range(N-1, -1, -1): #뒤에서부터  다이나믹 프로그래밍
    day = work_pay[i][0]
    pay = work_pay[i][1]
    
    if day > N - i: #남은 기간보다 상담일이 길 경우
        if i != N-1:  
            max_pay[i] = max_pay[i+1] #이전 최댓값 저장
        continue
        
    if i == N-1: #마지막 날 하루짜리 상담
        max_pay[i] = pay 
    elif i + day == N: #현재 일을 시작하면 정확히 마지막에 끝나는 경우
        max_pay[i] = max(pay, max_pay[i+1])
    else:
        #현재 일을 맡을 경우 or 맡지 않을 경우
        max_pay[i] = max(pay + max_pay[i + day], max_pay[i+1])
        
print(max_pay[0])