[Python] 백준 14502. 퇴사 (DP)

문제 링크

문제 풀이

• dp를 이용하여 i번째 날까지 받을 수 있는 최대 금액을 기록
• 전 기록을 이용하여 마지막 날까지 기록
• 마지막 날의 기록인 dp[-1]을 출력
• 단, N+1일째 이후까지 이어지는 상담을 고려할 필요가 없기 때문에,
  dp의 size는 n + 1까지 설정하고, dp 크기를 넘어서는 접근이 있을 경우
  try-except 문으로 그 상담은 고려 안하도록 설정
  • 왜 크기가 n이 아닌 n+1인 이유: 전 날의 기록을 고려해야 하기 때문에 편리성을 위해 0번쨰 날을 추가했기 때문

Point

i번째 날까지 얻을 수 있는 금액을 기록할 때, 두 가지를 유념해야 함

• 최대 금액을 기록하기 위해선 (새로운 상담에 대한 금액 + 전 상담들 대한 금액)을 더해주어야 한다.
  • 즉, i번째 날부터 t 기간이 걸리는 상담을 한다고 할 때, dp[i + t - 1] = p + dp[i-1]을 해줘야 한다.
  • 단, 특정 날까지 할 수 있는 상담들의 조합이 다를 수 있기 때문에,
    기존 기록 dp[i + t - 1]과 새로 계산한 최대 금액 p + dp[i-1] 중 더 큰 값으로 저장해줘야 한다.
    기존 기록이 더 클 경우, 새로 계산한 최대 금액을 저장할 필요가 없기 때문.
    그래서 dp[i + t - 1] = max(dp[i + t - 1], p + dp[i - 1] 해줘야 함
• i번째 날까지의 최대 금액은 전날인 i-1번쨰 날까지의 최대 금액을 이어받을 수 있다.
  • 즉, dp[i]는 dp[i-1]이 될 수 있다.
  • 단, 특정 날까지 할 수 있는 상담들의 조합이 다를 수 있기 때문에,
    dp[i] = max(dp[i], dp[i - 1] 해줘야 함.

코드

import sys

input = sys.stdin.readline

if __name__ == '__main__':
    n = int(input())
    t_p = [[0, 0]] + [list(map(int, input().split())) for _ in range(n)]
    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        t, p = t_p[i]
        try:
            dp[i] = max(dp[i], dp[i - 1])
            dp[i + t - 1] = max(dp[i + t - 1], p + dp[i - 1])
        except IndexError:
            continue
    print(dp[-1])