[백준] 14501 파이썬(python) : 퇴사 - (★)

14501번 : 퇴사

 

 

import sys
n = int(sys.stdin.readline())
dp = [0]*16 #1
t, p = [], [] #2
for _ in range(n):
    x, y = map(int, sys.stdin.readline().split())
    t.append(x) #3
    p.append(y)
for i in range(n-1, -1, -1): #4
    time = i + t[i] #5
    if time <= n: #6
        dp[i] = max(p[i] + dp[time], dp[i+1]) #7
    else: #8
        dp[i] = dp[i+1]
print(dp[0]) #9

 

#1 : 퇴사하기까지 남은 날을 dp테이블로 초기화(1 <= N <= 15 이어서 16으로 초기화)

#2 : 기간과 금액을 입력 받을 수 있는 리스트 선언

#3 : 입력받은 값 각각의 리스트에 삽입

#4 : 리스트의 마지막 인덱스부터 첫 인덱스까지 거꾸로 반복 (두번째 인자가 -1이면 인덱스 0까지 반복)

#5 : 오늘의 날짜와 기간을 합친 끝나는 날짜 변수 생성

#6 : 상담이 끝나는 날짜가 n보다 크거나 같다면(n+1일이 되는날 퇴사하기 때문에)

#7 : 점화식 생성

dp테이블은 지금까지 받을 수 있는 금액의 최고점. 그래서 현재날짜의 금액 p[i]과 현재 상담이 끝난날부터 마지막까지의 최고금액 dp[time]을 합한 값과 오늘의 다음날 i+1의 dp[i+1]을 비교해서 dp[i]에 삽입

#8 : 오늘 진행하는 상담의 끝나는 날이 퇴사하는날을 초과한다면 상담을 진행할 수 없으므로 다음날의 누적 최대 금액을 오늘의 dp[i]값으로 저장한다

#9 : 첫날의 dp값인 dp[0]을 출력하면 최대의 상담금액이 나온다.

 

예시 1에서 dp[5], dp[6]은 상담이 끝나는 날이 n을 초과하므로 이전에 dp = [0]*16으로 초기화 해두었던 dp[i+1]을 입력받아 0이 된다.

 

바텀업 방식을 낮은 숫자에서 큰 숫자가 아닌 큰 숫자에서 작은 숫자로 순환해 주는것이 다른 문제와의 차이점인것 같다. 점화식은 세우기 어려운것 같다.

 

---

작은 수부터 올라가는 바텀업 방식 문제

1904번 : 01타일