[백준] #14501 퇴사 (python)

14501번: 퇴사

 

 

문제풀이

import sys
from collections import defaultdict
input=sys.stdin.readline

day={}
price={}
result=defaultdict(int)



N=int(input())
for i in range(0,N):
    T,P=map(int,input().split())
    day[i]=T
    price[i]=P


for i in range(N-1,-1,-1):

    if day[i]+i>N:
        result[i]=result[i+1]
    else:
        result[i]=max(price[i]+result[i+day[i]],result[i+1])

print(result[0])

정리

뒤에서부터 DP를 풀면된다.

for i in range(N-1,-1,-1) : n일차부터 1일 차까지 작아지면서 반복

 

result = defaultdict(int) 을 통해 result 딕셔너리의 값들을 모두 0으로 초기화 해주었다.

경우의 수는 크게 2가지

 

1. 상담을 하면 퇴사일을 넘어가는 경우

i일차에 i일차가 걸리는 상담을 하게 되면 해당 상담은 진행할 수  없으니 전에 구한 다음날의 값을 가져옴

 

2. 상담을 해도 퇴사일을 넘어가지 않는 경우

(1) i일에 상담을 할 경우

오늘 상담이 끝나고 그 이후에 상담으로 받는 보수 + 오늘 상담보수

 

(2) i일에 상담을 하지 않는 경우

오늘 상담을 하지 않고 그 이후에 받는 상담보수 (전에 구해놓은 상담보수임)

 

(1)과 (2)중 최대값을 저장한다.