[파이썬][백준 14501][그리디] 퇴사 - 컴도리돌이

---

14501번: 퇴사

---

풀이 과정

1.  걸리는 일수(t)와 현재 일수(i)의 합이 n을 넘어가면 안되기 때문에 t+i가 n을 넘어가면 현재 일수보다 앞에 있는 일수의 값을 갖고 온다.

2. n을 넘어가지 않으면 현재 일수(i)보다 앞에 있는 일수(i+1)와  i+t 일수에 p를 더한 값과 비교해서 큰 값을 할당해 준다.

---

풀이 코드

import sys; input = sys.stdin.readline
n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
dp = [0] * (n+ 1)
for i in range(n-1,-1,-1) :
  t,p = arr[i]
  if t + i <= n :
    dp[i] = max(dp[i+1],dp[i+t] + p)
  else :
    dp[i] = dp[i+1]
print(dp[0])