07. 계단오르는 경우의 수 구하기

07. 계단오르는 경우의 수 구하기
정해진 계단을 1칸, 2칸 선택해서 오를 수 있다.

끝까지 오르는 경우의 수를 구하라.

(0칸은 1 가지 경우라고 하자)

 

계단 4칸

1111

112

121

211

22

총 5가지 경우

 

풀이 1)

fib_cache={}
def staircase(n):
    if n<2:
        return 1
    if n in fib_cache:
        return fib_cache[n]
    else:
        temp=staircase(n-1) + staircase(n-2)
        fib_cache[n] = temp
        return temp
# 테스트
print(staircase(0))
print(staircase(6))
print(staircase(15))
print(staircase(25))
print(staircase(41))

# 결과
1
13
987
121393
267914296

 

 

풀이 2)

def staircase(n):
    a, b = 1, 1
    for i in range(n):
        a, b = b, a + b
    return a
    
# 테스트
print(staircase(0))
print(staircase(6))
print(staircase(15))
print(staircase(25))
print(staircase(41))

# 결과
1
13
987
121393
267914296