[파이썬] 백준 15486 퇴사 2

풀이를 이해하려고 고민을 많이 했다. 조합을 사용하려고 했지만 안해봐도 시간 초과였고, dp 를 사용하는 건 알았다. 하지만 어떻게 구성을 해야 하는지 고민을 했는데 몰라서 구글링 했다. 

 

dp 를 생성을 우선 해준다. 마감일을 기준으로 [기존 마감일 까지의 수익]  과 [새로운 마감일의 수익] 의 최댓값을  dp 에 저장을 해주는 방식이다. 

from sys import stdin
 
N = int(stdin.readline())
dp = [0]*(N+1)
for i in range(1, N+1):
    t, p = map(int, stdin.readline().split())
    dp[i] = max(dp[i-1], dp[i])
    if i+t<=N+1:
        dp[i+t-1] = max(dp[i-1]+p, dp[i+t-1])
 
print(dp[-1])