[python] 백준 15486 퇴사2

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

15486번: 퇴사 2

 

문제해결

• DP를 어떻게 쓸지 처음에 막막했다.
• dp[i]를 i 번째 요일까지 일 했을 때 최대 이익이라고 정의하고 M을 통해 실시간으로 최대 이익을 계산하면 된다.

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
time, point = [], []
dp = [0]*(n+1)
for i in range(n):
    x, y = map(int, input().split())
    time.append(x)
    point.append(y)
M = 0
for i in range(n):
    M = max(M,dp[i])
    if i + time[i] >n: continue
    dp[i+time[i]] = max(M+point[i], dp[i+time[i]])
dp[n] = max(M,dp[n])
print(dp[n])