[백준]14501번: 퇴사

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

14501번: 퇴사

---

dp 문제!

 

크기가 n인 dp 테이블을 만들고 0으로 초기화한다.

x일차에 상담을 했을 경우 그 기간동안의 누적수익이 커질 경우에만 dp테이블 값을 증가시켜준다.

 

import sys 
input = sys.stdin.readline

n = int(input())
time = [0]*n
price = [0]*n

for i in range(n):
  t, p = map(int,input().split())
  time[i] = t
  price[i] = p

dp = [0]*(n+1)
for i in range(n):
  j = i + time[i]
  while j <= n:
    dp[j] = max(dp[j], price[i]+dp[i])
    j += 1

print(dp[n])