728x90
분석
네트워크 선자르기 (Bottom-Up, Top-Down)
bottom up """ 현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면 5가지 방법을 생각할 수 있습니다 1) 1m+1m+1m+1m 2) 2m+1m+1m 3) 1m+2m+1m 4) 1m+1m+2m
karla.tistory.com
풀이
"""
철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다.
만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.
그렇다면 총 N계단일 때 올라가는 방법의 수를 출력
계단의 개수인 자연수 N(3≤N≤45)
"""
n = int(input())
d = [0]*(n+1)
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