[백준 14501번] 퇴사 -python

문제 링크

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

14501번: 퇴사

 

풀이

- 완전 탐색 공부하다가 dp 문제를 봐버려서 ... dp 다시 공부하러 감 

- 메모제이션 문제 

- 뒤에서부터 계산 

- 예제를 표로 계산해보면 아래와 같음. dp[0]에는 최댓값이 들어가 있음 

n = int(input())

t = []
p = []

for _ in range(n):
  a, b = map(int,input().split())
  t.append(a)
  p.append(b)

d = [0] * (n+1)

for i in range(n-1, -1 ,-1):
  # i번째에 일을 하는 게 n을 초과하면 일을 하지 않음 
  if t[i] + i > n:
      d[i] = d[i+1]
  # i번째에 일을 하는 것과 일을 안하는 것 중 최댓값 
  else:
    d[i] = max(d[i+1], p[i] + d[i +t[i]])

print(d[0])