[알고리즘] 코드잇 - 출근하는 방법1(Python)

설명

영훈이는 출근할 때 계단을 통해 사무실로 가는데요. 급할 때는 두 계단씩 올라가고 여유 있을 때는 한 계단씩 올라 갑니다.

 

어느날 문득, 호기심이 생겼습니다. 한 계단 또는 두 계단씩 올라가서 끝까지 올라가는 방법은 총 몇가지가 있을까요?

 

계단 4개를 올라간다고 가정하면, 이런 방법들이 있습니다.

- 1, 1, 1, 1

- 2, 1, 1

- 1, 2, 1

- 1, 1, 2

- 2, 2

총 5개 방법이 있네요.

 

함수 staircase()는 파라미터로 계단 수 n을 받고, 올라갈 수 있는 방법의 수를 효율적으로 찾아서 리턴합니다.

 

힌트1

계단의 높이가 4인 경우를 생각해 봅시다.

 

- 0 -> 1 -> 2 -> 3 -> 4

- 0 -> 1 -> 2 -> 4

- 0 -> 1 -> 3 -> 4

- 0 -> 2 -> 3 -> 4

- 0 -> 2 -> 4

매번 오를 수 있는 계단의수는 1 또는 2입니다. 따라서 4번 계단으로가기 위해서는 결국 3번 계단 또는 2번 계단에서 올라가야합니다.

 

이걸 일반화하면 어떻게 될까요?

 

힌트2

n번 계단으로 가기 위해서는 n - 1 번 계단 또는 n - 2번 계단에서 올라가야 합니다.

이걸 코드로 어떻게 표현할 수 있을까요?

 

힌트3

수학적으로 staircase(n)은 staircase(n -1) + staircase(n -2)로 표현이 가능합니다. 어디서 많이 보던 연산 아닌가요?

 

힌트4

n번째 피보나치 수를 계산해 주는 함수 fib(n) 은 fib(n-1)+fib(n-2)로 표현됩니다. 사실 이 문제는 피보나치 수열 문제와 거의 똑같은 거죠.

fib(n)		1	1	2	3	5	8	13	21
staircase(n)	1	1	2	3	5	8	13	21	34

 

 

 

답안

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))