Bottom-Up 방식
문제는 이해했는데 ‘이걸 어떻게 구현하지’라는 생각에 문제를 해결하기까지 꼬박 이틀이 걸렸다. 예제들을 직접 손으로 그려보기도 하고, 문제를 다시 분석해보면서 해결책을 찾았다. Bottom-Up 방식이 그나마 직관적이고 이해하기 편해서 다음과 같이 구현했다. 0에서 n까지 index에 대해서 이중 max()로 값을 비교하고 최대 기댓값을 산출하는 알고리즘을 구현했다.
# 입력
import sys
n = int(sys.stdin.readline())
work = list(tuple(map(int, sys.stdin.readline().split())) for i in range(n))
dp = [0] * (n+1)
# 처리
# bottom-up 방식
for i in range(n):
if i+work[i][0] <= n:
dp[i+work[i][0]] = max(dp[i+work[i][0]], max(dp[:i+1]) + work[i][1])
print(max(dp))
Top-Down 방식
아무리 고민해도 Top-Down 방식 구현이 어려워서 다른 블로그들을 참고했다. 예시 꾸준히 공부해나가면서 다른 접근으로도 풀어낼 수 있도록 실력을 키워야겠다.