백준 14501 퇴사 파이썬 문제풀이 (python 기억, 탑다운 DP, 메모이제이션)

문제 보러가기

 

백준 퇴사 파이썬 문제풀이 DP

이전 포스팅에서는 퇴사 문제를 재귀함수만을 이용해서 풀었는데,

다른 방법으로 DP 다이나믹 프로그래밍 기법으로 풀어보도록 하자.

 

그러면 이전까지의 경험 중 가장 좋은 것을 선택해서 저장하는 메모이제이션 방법을 이용한다.

정답 코드

n = int(input())
work = []
answer = 0
def recur(day):
    global answer
    if day > n:
        return float("-inf")
    if day == n:
        return 0

    # 더 가격이 높은 경우를 dp에 저장
    dp[day] = max(
        recur(day+work[day][0]) +work[day][1],
        recur(day+1)
    )
    return dp[day]

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

dp = [-1 for _ in range(n+1)]
recur(0)
print(max(dp))

dp에 더 높은 가격을 저장하는 방식으로 재귀를 호출했다. 

 

우선 dp를 선언하고 재귀함수 안에서는

현재 day dp에 day 상담을 채택하는 케이스와 다음으로 그냥 넘어가는 케이스 중 큰 값을 저장하고,

각각 케이스에 대한 재귀를 수행한다.

 

재귀는 일자가 오버되면 안되니 아주 작은 값으로 설정하고,

일자가 딱 맞게 끝나면 0을 반환하여 dp에 반환 저장되도록 돌려보낸다.

 

이렇게 재귀가 모두 돌면, 첫 번째 dp에는 그 다음 일자들의 케이스들에 대한 최댓값이 들어갈 것이다.

정답이다!

 

    if dp[day] != -1: # dp값이 있는 경우
        return dp[day]

추가적으로 시간을 줄이기 위해서 

dp값이 이미 있다면 재귀하지 않고 그대로 반환하는 것이 최적화 방법이다.