728x90
bottom up
"""
현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다.
예를 들어 4m의 네트워크 선이 주어진다면 5가지 방법을 생각할 수 있습니다
1) 1m+1m+1m+1m
2) 2m+1m+1m
3) 1m+2m+1m
4) 1m+1m+2m
5) 2m+2m
네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법?
첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.
"""
# Bottom-Up
n=int(input())
d=[0]*(n+1)
d[1]=1
d[2]=2
for i in range(3,n+1):
d[i]=d[i-1]+d[i-2]
print(d)
print(d[n])
top down
n=int(input())
d=[0]*(n+1)
d[1]=1
d[2]=2
def dfs(len):
if d[len]>0:
return d[len]
if len==1 or len==2:
return len
else:
d[len]=dfs(len-1)+dfs(len-2)
return d[len]
print(dfs(n))
728x90