출근하는 방법 I

출근하는방법I.py

# 시간 복잡도 O(n)
def staircase(n):
    # 여기에 코드를 작성하세요
    a, b = 1, 1
    for i in range(n):
        temp = a
        a = b
        b = temp + b
        
    return a

# 테스트 코드
print(staircase(0))
print(staircase(6))
print(staircase(15))
print(staircase(25))
print(staircase(41))

해결과정

계단의 높이가 4인 경우를 생각해보면

• 0 → 1 → 2 → 3 → 4
• 0 → 1 → 2 → 4
• 0 → 1 → 3 → 4
• 0 → 2 → 3 → 4
• 0 → 2 → 4

매번 오를 수 있는 계단의 수는 1 또는 2이다. 따라서 계단으로 가기 위해선 결국 3번째 계단 또는 2번째 계단에서 올라가야하는데, 이걸 일반화 한다면, staircase(n) = staircase(n-1) + staircase(n-2)로 표현이 가능하다.

 

피보나치 수열도 fib(n) = fib(n - 1) + fib(n - 2)로 표현된다.

정확히 얘기하면, staircase(n) 과 fib(n+1)이 동일한 셈이다.