티스토리 뷰

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

* dp[i] = i번째 날까지의 최대 금액

import sys

N = int(sys.stdin.readline())

day = N
T, P = [], []
dp = [0]*(N+1)

for i in range(N):
    temp = list(map(int, sys.stdin.readline().split()))
    T.append(temp[0])
    P.append(temp[1])


for i in range(0, N):
    if T[i] <= N - i:
        dp[i+T[i]] = max(dp[i+T[i]], dp[i]+P[i])
        
    dp[i+1] = max(dp[i+1], dp[i])

print(dp[N])

'Algorithm > Baekjoon' 카테고리의 다른 글

[백준] 2606 : 바이러스 - Python  (0) 2020.03.20
[백준] 1260 : DFS와 BFS - Python  (0) 2020.03.20
[백준] 6378 : 디지털 루트 - Python  (0) 2020.03.14
[백준] 2231 : 분해합  (0) 2020.03.13
[백준] 2798 : 블랙잭 - Python  (0) 2020.03.13
공지사항
최근에 올라온 글
«   2025/02   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함