[백준/DP] 15486 퇴사2 (Python, 파이썬)

 

 

www.acmicpc.net/problem/15486 

15486번: 퇴사 2

import sys
input=sys.stdin.readline

n=int(input())
T=[]
P=[]
for _ in range(n):
    a, b=map(int, input().split())
    T.append(a)
    P.append(b)

# DP 테이블 초기화
dp=[0]*(n+1)

for i in range(n):
	# 앞으로 남은 날(n-i) 안에 끝날 수 있다면
    if T[i] <= n-i:
    	# 일이 끝나는 날(i+T[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])