백준 14501 퇴사 - 파이썬(Python)

 

백준 14501번

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

14501번: 퇴사

 

정답코드

- dp[i]는 i번째 날까지 일했을 때의 최대 수익이다.

- 처음에는 dp의 모든 원소를 0으로 설정한다.

- 먼저 현재 날의 최대 수익은, 기존 현재 날의 최대 수익(dp[i])과, 전날까지의 최대 수익(dp[i-1]) 중 더 큰 값으로 설정한다.

- 그 후, 현재 날의 상담을 수행하기 위해 필요한 날이 상담 가능한 마지막 날짜를 넘어서지 않는지 체크하여, 넘어설 경우 패쓰한다.

- 현재 날의 상담을 수행해서 상담을 마친 날의 최대 수익(dp[i+t-1])은, 그 날의 기존 최대 수익과, 현재 날의 전날까지의 최대 수익(dp[i-1])에 상담을 해서 받는 수익(p)을 합한 값 중 더 큰 값으로 설정한다.

- 마지막날까지 계산한 뒤, 최대값을 갖고 있을 dp[-1]을 출력한다.

 

n=int(input())
dp=[0]*(n+1)
for i in range(1,n+1):
    t,p=map(int, input().split())
    dp[i]=max(dp[i], dp[i-1])
    if i+t-1 <= n:
        dp[i+t-1]=max(dp[i+t-1], p + dp[i-1])
print(dp[-1])