[김태원 알고리즘] 네트워크 선 자르기 (DP)

사용 언어: Python3

문제

풀이

Bottom-Up

원래는 Bottom-Up 방식이 “진짜” 동적계획법이고, Top-Down 방식은 넓은 의미에서 동적계획법인 것이다.

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])

• 정답!
• 다이나믹 프로그래밍 문제를 풀기 위해서는 아래처럼 점화식을 도출해내면 된다.

Top-Down: 재귀, 메모이제이션

메모이제이션: 구해진 값들을 기록 해두고 cut edge를 통해 불필요한 재귀 호출을 방지한다.

import sys
sys.setrecursionlimit(10**6)

def DFS(length):
    if dp[length] != 0: # ✅ 메모이제이션을 통한 cut edge
        return dp[length]
    if length == 1 or length == 2:
        return length
    else:
        dp[length] = DFS(length-2) + DFS(length-1)
        return dp[length]

N = int(input())
dp = [0] * (N+1)
print(DFS(N))

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기