[백준/BOJ] 14501번 - 퇴사

What ?

👉 https://www.acmicpc.net/problem/14501

상담을 완료하는 데 걸리는 기간과 상담했을 때 받을 수 있는 금액이 주어졌을 때, 최대 수익을 구한다.

How ?

N = int(input())
table = [list(map(int, input().split())) for _ in range(N)]

dp = [0] * (N+1)
result = 0
for i in range(N-1, -1, -1):
    time = table[i][0] + i

    if time < N+1:
        dp[i] = max(dp[time] + table[i][1], result)
        result = dp[i]
    else:
        dp[i] = result

print(dp[0])

⚡ 다이나믹 프로그래밍

• 뒤에서부터 검사하면서 해당 날짜에 상담할지 말지를 결정해줬다.
• 상담할 경우 최대 수익값을 구해 DP table을 갱신하는 방식으로 해결했다.