[삼성/코테기출][Python][백준][14501] 퇴사 (완전탐색/DP)

🍋 문제링크

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

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 121220 KB

시간 : 112 ms

🍓 문제풀이

🍉 Code

N = int(input())
time = [0 for _ in range(N)]
pay = [0 for _ in range(N)]
DP = [0 for _ in range(N+1)]

for i in range(N):
    tmp = list(map(int, input().split()))
    time[i] = tmp[0]
    pay[i] = tmp[1]

DP[N] = 0
for i in range(N-1, -1, -1):
    if (N-i) < time[i]:
        DP[i] = DP[i+1]
    else:
        DP[i] = max(pay[i] + DP[i+time[i]], DP[i+1])

print(DP[0])