[백준] 15486번: 퇴사 2

문제

백준 - 15486번: 퇴사 2

분석

상담 일정에 대한 정보로 걸리는 시간과 받는 금액이 주어졌을 때, 퇴사 전에 할 수 있는 최대 수익을 구하는 문제이다.

상담이 진행되는 기간은 다른 상담을 할 수 없는데, 그 미래 상황을 모르기 때문에 dp 값을 채워나가려면 뒤에서부터 진행한다.

현재 참고하는 날짜에서 걸리는 상담 일 수를 더했을 때 퇴사일이 넘어가는지를 먼저 본다.
넘어간다면 상담이 불가능하므로 바로 직전에 계산한 값(다음 날 dp)을 가져온다. 인덱스 오류 방지를 위해 dp 크기는 (n+1)로 초기화한다.
퇴사일이 넘어가지 않는다면, 현재 상담이 끝난 시점의 dp값에 현재 상담의 상담료를 더한 값을 더하고 이 값을 바로 직전에 계산한 값(다음 날 dp)와 비교하여 더 큰 값을 취한다.

가장 큰 이익은 dp[0]를 출력하면 된다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n = int(input())
info = []
for _ in range(n):
    t, p = map(int, input().split())
    info.append((t, p))
dp = [0]*(n+1)
for i in range(n-1, -1, -1):
    t, p = info[i]
    if i + t <= n:
        dp[i] = max(dp[i+1], dp[i+t]+p)
    else:
        dp[i] = dp[i+1]
print(dp[0])

끝으로..

뒤에서부터 진행하는 dp 문제를 풀어봤는데, 이런 문제를 더 많이 접해봐야겠다.