[Baekjoon] 14501. 퇴사

🔗 Problem Link

14501번: 퇴사

---

❔Thinking

• 상담에 걸리는 시간과 상담에 따른 이익이 주어질 때, N+1일 이후에 얻게되는 최대 이익을 반환한다.

---

💻Solution

n = int(input())
dp = [0] * (n+1)
table = []
max_price = 0

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

print(max_price)

---

🗝️keypoint

1. 상담은 하루에 한번만 가능하며 N일까지 상담이 끝나지 않으면 진행할 수 없으므로, DP를 마지막부터 시행한다.
2. 차례대로 수행되는 일련의 과정에서 특정 지점의 값을 알아내려면, DP를 활용한다.