[BOJ/python] 15486: 퇴사 2

문제

✔️ gold 5
다이나믹 프로그래밍

문제 흐름

퇴사 직전 날짜 n부터 1까지 거꾸로 올라가며 계산을 진행했다.
time에 상담 기간, price에 상담 수익을 저장한다.
memo[x]에 퇴사일부터 x일까지의 최대 수익을 저장했다.
초기값은 memo[n - 1]으로 마지막 날의 상담 기간이 1인 경우 마지막 상담 수익, 그보다 큰 경우 0을 저장했다.
이후 날짜 x에 대하여 n-2부터 0까지 memo[x]를 계산한다.

• memo[x]의 계산
  • x일의 상담을 하는 경우
    ➡️ (x + time)일이 x일의 상담을 끝낸 뒤 다음 상담 가능일
    ➡️ x일의 상담 수익 + (x + time)일 까지의 최대 수익
  • x일의 상담을 하지 않는 경우
    ➡️ (x - 1)일 까지의 최대 수익과 동일
  • 위의 두 경우 중 더 큰 값을 채택

코드

# 퇴사 2
# dp greedy

import sys
input = sys.stdin.readline

def dp (n: int, time: list, price: list):
    memo = [0 for i in range(n + 1)]
    if n == 1:
        if time[0] > 1:
            return 0
        else:
            return price[0]
    
    if time[n - 1] > 1:
        memo[n - 1] = 0
    else:
        memo[n - 1] = price[n - 1]
    for x in range(n - 2, -1, -1):
        if x + time[x] - 1 < n:
            memo[x] = max(memo[x + 1], memo[x + time[x]] + price[x])
        else:
            memo[x] = memo[x + 1]
    # print(memo)
    return memo[0]

if __name__ == "__main__":
    n = int(input())
    time = []
    price = []
    for i in range(n):
        t, p = map(int, input().split())
        time.append(t)
        price.append(p)
    
    result = dp(n, time, price)
    print(result)

마무리

문제를 어떻게 풀어야하나 고민을 정말 많이 했다.
실버 문제를 풀다가 좀 적응이 됐나 싶어 골드로 넘어오니 확실히 갈피도 못잡고 헤맸다.. ㅠ
과거 상담의 선택 여부가 미래 상담의 선택 여부에 영향을 미치니 어떻게 접근해야할지 고민을 많이 했는데, 정말 알까말까 싶은 느낌에 너무 오랜 시간을 고민하게 되어 또 ChatGPT에게 힌트를 받았다.
dp는 적응 될 때까지 풀이 코드 리뷰하고 여러 문제를 꾸준히 풀어보는게 좋을 것 같다.