퇴사 [백준 14501] - python

import sys
input = sys.stdin.readline

def BOJ14501() :
  n = int(input())
  work = []
  for _ in range(n) :
    work.append(list(map(int, input().split())))

  dp = [0 for _ in range(n+1)]
  day, cost = work[0]

  for i in range(n-1, -1, -1) :
    day, cost = work[i]
    
    complete_day = i + day
    if complete_day <= n :
      dp[i] = max(dp[i+1], dp[complete_day] + cost)
    else :
      dp[i] = dp[i+1]
    
  print(dp[0])
BOJ14501()

접근 방법 :

1. 끝에서부터 탐색을 하였고 현재 수행할 수 있는 일이 이전에 했던 일들에 영향을 받으므로 dp를 이용하였습니다.

2. 6일과 7일의 경우 완료기간이 퇴사하는 날짜보다 이후이므로 탐색의 대상이 아닙니다.

3. n일 일때 dp[n]은

 

완료날짜에서의 최댓값 + 현재 일을 수행하는 값

                                vs

이전날짜의 최댓값중 큰 값을 넣어주면 됩니다.

 

4. 입력값에서 최대 수익은 dp[0] 배열에 위치하게 됩니다.

 

 

 

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

14501번: 퇴사