๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/14501
์ฝ๋ ์ ์ถ ๊ธฐ๋ก (๋ฉ๋ชจ๋ฆฌ ๋ฐ ์๊ฐ)
์ ์ถ ๋ ์ง
@4/22/2021
๋ฉ๋ชจ๋ฆฌ
121220 KB
์๊ฐ
112 ms
๋ฉ๋ชจ
โข
์ผ์ฑ sw ์ฝ๋ฉํ
์คํธ ๊ธฐ์ถ
๋ฌธ์ ํ์ด
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])
Python
๋ณต์ฌ