매번 dp로 풀엇지만 브루트포스로도 풀린다고 한다. 처음부터 더해서 최댓값갱신. 다음 기회에는 풀어보는걸로,
import sys
input = sys.stdin.readline
N = int(input())
T = []
P = []
dp = []
for i in range(N):
a, b = map(int, input().split())
T.append(a)
P.append(b)
dp.append(b)
dp.append(0)
for i in range(N - 1, -1, -1):
if i + T[i] > N:
dp[i] = dp[i + 1]
else:
dp[i] = max(dp[i + 1], P[i] + dp[i + T[i]])
print(dp[0])
'practivceAlgorithm > 백준' 카테고리의 다른 글
[백준][Python] 20055 컨베이어벨트위의 로봇 (0) | 2021.08.05 |
---|---|
[백준][Python] 7511 소셜네트워킹 (0) | 2021.08.05 |
[백준][Python] 5972 택배배송 (0) | 2021.08.03 |
[백준][Python] 2042 구간합구하기 (0) | 2021.08.03 |
[백준][Python] 1561 놀이공원 (0) | 2021.08.03 |