DFS

dfs(7)
6m를 자르는 경우의 수 +1(m)
5m를 자르는 경우의 수 +2(m)
.
.
.

DFS(7) = DFS(6) + DFS(5)
DFS(6) = DFS(5) + DFS(4)
.
.
.
DFS(3) = DFS(2) + DFS(1)
이를
dy 배열에 저장한다.
1 2 3 4 5 6 7
□□□□□□□□

네트워크 선 자르기

Bottom-Up 방식

import sys

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

def input():
    return sys.stdin.readline().rstrip()

def DFS(len):
    if dy[len]>0: # 시간 줄이기 위한 가지 컷.. len에 값이 있으면 return 바로 해라.
        return dy[len]

    if len == 1 or len == 2:#종착점
        return len
    else:
        dy[len]=DFS(len-1)+DFS(len-2) #메모이제이션(기록 테이블)
        return dy[len] 


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