백준 154866. 퇴사 2

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

15486번: 퇴사 2

import sys
input = sys.stdin.readline

N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
dp = [0] * (N+1)
max_p = 0
for i in range(N):
    max_p = max(max_p,dp[i]) # 현재 저장된 돈을 이전 최대 금액과 비교
    end = i + arr[i][0] # 일이 끝나는 날로 갱신
    if end <= N: # 일을 그만두기 전에 끝난다면?
        dp[end] = max(max_p + arr[i][1], dp[end]) # 이전 최대 금액과 끝나는 날의 버는 돈을 비교
print(max(dp)) # 벌 수 있는 가장 큰 금액 출력