백준 14501번 파이썬 _ 퇴사

www.acmicpc.net/problem/14501

14501번: 퇴사

문제유형 : DP

 

문제핵심 : 뒤에서부터 확인해서 DP값을 갱신하는것

 

아래 두 값중에 더 큰값으로 갱신이 이루어진다 

• i번째 일을 할때의 이익 ( = i번째일의 이익 + i번째일을 하는데 걸리는시간후의 이익)  : cost[i]+dp[i+day[i]])
• i번째 일을 건너뛰고 i+1번째 일을 할때의 이익 : dp[i+1]

핵심 점화식 :   dp[i] = max(dp[i+1], cost[i]+dp[i+day[i]])

 

둘중에 더 큰값으로 dp[i]값을 갱신하고 최종적으로 dp[0]의 값이 최대가된다

n = int(input())
day = []
cost = []
dp=[]

for i in range(n):
  x,y = map(int, input().split())
  day.append(x)
  cost.append(y)
  dp.append(y)
dp.append(0)  #뒤에 0을 추가해서 인덱스초과 오류 방지

#뒤에서부터 확인
for i in range(n-1, -1, -1):
  if day[i] + i > n: #데드라인이 기한을 넘어가는경우
    dp[i] = dp[i+1]
  else:
    dp[i] = max(dp[i+1], cost[i]+dp[i+day[i]])

print(dp[0])