algorithm

[백준/python] 15486 - 퇴사2

현재의 현제 2022. 9. 7. 13:36

 

15486번: 퇴사 2

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

www.acmicpc.net

n = int(input())
sch = [
    tuple(map(int, input().split()))
    for _ in range(n)
]
dp = [0 for _ in range(n+1)]

print(dp)

if sch[n - 1][0] == 1:
    dp[n - 1] = sch[n - 1][1]
else:
    dp[n - 1] = 0

for i in range(n - 2, -1, -1):
    if i + sch[i][0]> n:
        dp[i] = dp[i + 1]
    else:
        dp[i] = max(dp[i + 1], sch[i][1] + dp[i + sch[i][0]])

print(dp[0])

dp 변수만 바꿔 주었더니 되었다. 퇴사 1이랑 완전 똑같은 문제. 왜인지 모르게 python으로 하면 시간초과 나길래 파이파이로 했더니 됐다. 굿~