[백준][동적 계획법1] 14501. 퇴사 (파이썬/Python)

import sys
input = sys.stdin.readline

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

dp = [0 for _ in range(n+1)]

for i in range(n-1,-1,-1):
    if i + timetable[i][0] > n:
        dp[i]= dp[i+1]

    else:
        dp[i] = max(timetable[i][1]  +dp[i+timetable[i][0]],dp[i+1])
print(dp[0])

# 뒤에서부터 살펴보면서 주어진 시간보다 더 뒤에 있는 것들은 수행할 수 없으니 if문으로 구분해가며 진행한다.