자료구조와 알고리즘/개인적인 코딩테스트 관련 풀이
[동적 계획법][Bottom-Up] - 네트워크 선 자르기
얄루몬
2022. 8. 16. 14:38
n = int(input())
dp = [0]*(n+1)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-2] + dp[i-1]
print(dp[n])
- 가장 작은 해를 구해 그 해를 이용해서 점차 다른 큰 해를 구하는 점화식을 Bottom-up 방식이라 한다.
- DP의 경우 기준점이되는 부분을 잘 찾아서 이를 이용하면 문제를 쉽게 해결할 수 있다.
- Bottom-Up 방식이 동적계획법이고 Top-Down 방식은 넓은 의미의 동적 계획법이다.