[BaekJoon] 백준 14501번 퇴사

[BaekJoon] 백준 -번 문제이름

 

🎈문제

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

💬설명

• 전형적인 dp 문제
• 점화식은 다음과 같다.
• dp(n) = (n번째날 ~ 마지막 날) 최대 수익 이라고 할 때
• dp(n) = max( dp(n+1), P[n] + dp(n + T[n]] )
• 말로 풀어서 말하자면
• (n번째 날부터 마지막 날까지의 최대 수익)은 (n+1번째 날 ~ 마지막 날까지의 최대 수익)과 (n번째 날의 수익 + (n + Tn)번째 날부터 마지막 날까지의 최대 수익) 중 더 큰 값이다.
• 주어진 예시를 뒤에서부터 따져보면 이해가 간다.

👩‍💻코드

# BaekJoon14501.py

N = int(input())
T = [0 for _ in range(N)]
P = [0 for _ in range(N)]
for i in range(N):
    T[i], P[i] = map(int, input().split())
dp = [0 for _ in range(N + 1)]

for i in range(N - 1, -1, -1):
    if N - i < T[i]:
        dp[i] = dp[i + 1]
    else:
        dp[i] = max(dp[i + 1], P[i] + dp[i + T[i]])

print(dp[0])