[백준 14501번][실버3] 퇴사 (파이썬)

---

문제출처

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

14501번: 퇴사

---

문제를 스스로 해결하였는가? -> X

 실버3이라고 만만하게 봐서는 안되겠다. 알고리즘 분류를 참고해 DP문제임을 알았는데도 아이디어가 떠오르지 않아서 결국 구글링했다. 아이디어를 캐치하니 코드는 금방 짤 수 있었다. 물론 아이디어 캐치하는게 제일 중요한 문제겠지만.. 무튼 아이디어를 시각적으로 잘 그려낸 블로그가 있어서 링크남긴다. DP 좀 잘 풀고싶다...

---

알고리즘 분류

• DP

---

아이디어

• 퇴사일부터 역순으로 dp값을 계산해야한다.

---

전체코드

import sys
input = sys.stdin.readline
n = int(input())
arr = []
for _ in range(n):
    tmp = list(map(int, input().split(' ')))
    arr.append(tmp)

dp = [0] * (n+1)
for i in range(n-1, -1, -1):
    w,v = arr[i]
    if i + w > n:
        dp[i] = dp[i+1]
        continue
    dp[i] = max(dp[i+1], v + dp[w + i])
print(dp[0])