네트워크 선 자르기

가장 작은 해를 구하고, 점점 키워나가면서 앞에 구해놓은 해를 이용하여 현재 해를 구하고 ... n의 해를 구하고 최종적으로 필요한 해를 구한다 >> Bottom up 방식.
문제를 확장시켜서, 문제를 키워서 최종 결과를 내는 방식이다.

네트워크 선 자르기(Bottom-Up)

4m의 네트워크 선
1) 1m + 1m + 1m + 1m
2) 2m + 1m + 1m
3) 1m + 2m + 1m
4) 2m + 2m

dy라는 1차원 배열을 만들고,
1 2 3 4 5 6 7
□□□□□□□

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

n = int(input())
dy = [0]*(n+1)
dy[1] = 1
dy[2] = 1

for i in range(3, n+1):
    dy[i] = dy[i-1] + dy[i-2]
print(dy[n])