백준 14501 퇴사 파이썬 문제풀이 (python 바텀업 DP)

문제 보러가기

 

백준 퇴사 파이썬 문제풀이

또 보는 퇴사 문제. 

이번에는 또 다른 방법인 바텀업 DP로 풀어보자. 

 

정답코드

n = int(input())
work = []
answer = 0

for i in range(n):
    t,p = map(int,input().split())
    work.append([t,p])

dp = [0 for _ in range(n+1)]

for idx in range(n)[::-1]:
    if idx + work[idx][0] > n:
        dp[idx] = dp[idx+1]
    else:
        dp[idx] = max(dp[idx + work[idx][0]] + work[idx][1], dp[idx+1])

print(max(dp))

탑다운DP와는 다르게 반복문만으로 풀어낼 수 있지만

else 문에 있는 점화식을 도출하기는 쉽지 않다.

 

결국 마지막 순서에서부터 상담을 포함하는 경우 그렇지 않은 경우들의 최적값을 구해서

다음 값에 대한 dp로 현재 값을 결정한다.

이렇게 한 문제를 재귀로도 탑다운 DP로도 바텀업 DP로도 풀어보면서,

DP로 접근하는 방법을 이해하기도 해야하지만 어느정도는 외우는 감이 있다;;