[BOJ/python] 14501: 퇴사

문제

✔️ silver 3

dp

문제 흐름

이전에 정확하게 같은 문제를 풀었던 것 같은데..! 하는 생각이 스쳐지나갔다.
역시 퇴사 2문제를 풀었었다.
퇴사 2 문제와 완전히 같지만 인풋 조건이 퇴사 2보다 훨씬 작다는 점에서 더 쉬운 버전이다.
당시에도 어렵다고 느꼈었지만 이미 한 번 풀어본 상태에서도 흐름을 생각해내기 어려웠다.
복습은 중요함을 다시 깨닫고 간다...

일단 중요한건 memo의 역할 정의이다.
이 문제에서 memo[i]는 i번째 날부터 퇴사일까지 벌 수 있는 최대 금액이다.
따라서 퇴사일부터 앞으로 거꾸로 넘어오며 단계별로 계산하게 된다.
문제의 input인 t와 p의 값들을 time과 price변수를 생성해 저장하였는데,
time[i]값을 통해 i번째 날에 일을 할 경우 그 다음 근무 가능일을 예측 가능하기 때문에 뒤에서부터 계산하는 방식을 사용하게 된다.

뒤에서부터 시작하기 때문에 초기값으로 memo[-1]을 설정해줘야한다.
마지막날 상담 기간이 1인 경우 price[-1]만큼 벌 수 있고, 아닌 경우는 퇴사일을 넘기므로 벌 수 없다.
이렇게 설정해준 뒤 -2 인덱스부터 차례로 memo값을 계산한다.
나의 경우 음수 인덱스는 헷갈릴 수 있어서 전체 일수 n을 선언하고 n-2부터 시작해서 1씩 줄어들며 계산했다.

memo[i]가 가질 수 있는 값은 두가지 있다.

1. i번째 날 일을 안한다.
   ➡️ i+1번째 날부터 퇴사일까지 벌 수 있는 최대 금액
   ➡️ memo[i + 1]
2. i번째 날 일을 한다.
   ➡️ i번째 날의 상담 보수 금액 + i번째 날 상담이 끝난 다음날부터 퇴사일까지 벌 수 있는 최대 금액
   ➡️ i번째 날 상담이 끝난 다음날은 i + time[i]
   ➡️ price[i] + memo[i + time[i]]

이 두가지 중에서 더 큰 값을 memo[i]에 저장하면 된다.
이렇게 계속 구하면 0번째 날부터 퇴사일까지 벌 수 있는 최대 금액이 된다.

코드

# 퇴사
# DP

import sys
input = sys.stdin.readline

def dp (time: list, price: list):
    n = len(time)
    memo = [0 for i in range(n)]
    if time[-1] == 1:
        memo[-1] = price[-1]
    else:
        memo[-1] = 0
    
    i = n - 2
    while i >= 0:
        if i + time[i] < n:
            memo[i] = max(memo[i + 1], memo[i + time[i]] + price[i])
        elif i + time[i] == n:
            memo[i] = max(memo[i + 1], price[i])
        else:
            memo[i] = memo[i + 1]
        i -= 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(time, price)
    print(result)