Algorithm (PS)

[백준] 15486번: 퇴사 2

minjiwoo 2023. 1. 14. 18:35
728x90

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

 

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())
task = []
price = [] # price
dp = [0] * (n+1)

for _ in range(n):
    t, p = map(int, input().split())
    task.append(t)
    price.append(p)
# result 예제 10번에서 예외케이스 처리 -> dp[10]이 최댓값(60) + price[7] 로 갱신되어야 함
result = 0 # 이전의 dp 값들중 최댓값 저장하기
for i in range(n):
    result = max(dp[i], result)
    if i + task[i] >= n+1:
        continue
    dp[i+task[i]] = max(result+price[i], dp[i+task[i]])

print(max(dp))
728x90