Part7.2_동적프로그래밍(DynamicProgramming)_네트워크 선 자르기(Top-Down: 재귀, 메모이제이션)

DFS(7) 이면
7m 짜리 네트워크 선이 주어지면, 자르는 방법의 수를 retrun 받는 것,

6m 를 자르는 모든 경우의 수에 1 만 더하면 된다.
5m를 자르는 모든 경우의 수에 마지막에 2만 더하면 된다.
DFS(6) + DFS(7)
이것을 그래로 해주는 것

D(7)
↓
D(6) + D(5)
↓
D(5) + D(4)
↓
D(4) + D(3)
↓
D(3) + D(2)
↓
D(2) + D(1)
이런식으로 쭉 내려갈 것이다.전위순회,,

D(2) 는 2를 return 하면 되고 D(1) 는 1을 return 하면 된다.

dy 1 2 3 4 5 6 7
ㅡ□□□□□□□□ 에 가지 뻗은 것을 다시 위로 가면서 배열에 값을 추가한다,
D(7)
↑
D(6) + D(5)
↑
D(5) + D(4)
↑
D(4) + D(3) = . . .
↑
D(3) + D(2) = 3 + 2
↑
D(2) + D(1) = 2 + 1

dy 1 2 3 4 5 6 7
ㅡ□□□□□□□□
ㅡ 1 2 3 5 8 13 ...

미리 한번 구해진 것을 가지고 불필요한 호출을 제거하는 것이 메모이제이션이다.

import sys
sys.stdin = open("input.txt", "rt")

def DFS(len):
    if dy[len] > 0:
        return dy[len]
# 가지를 cut 하는 방법
    if len == 1 or len == 2:
        return len
    else:
        dy[len] = DFS(len-1) + DFS(len-2)
        #dy[7] = D(6) + D(5)
        return dy[len]


if __name__=="__main__":
    n = int(input())
    dy=[0]*(n+1)
    print(DFS(n))