[Python] 코드업 2632 : 계단 오르기1 풀이

codeup.kr/problem.php?id=2632

계단 오르기 1

n번째 계단을 오르는 경우의 수는

n-2번째 계단을 두번 오르는 수와 n-1번째 계단을 한번 오르는 수의 합이다.

 

예를 들어서 확인해보면,

1번째 계단을 오르는 수는 -1번째 계단을 두번 오르는 수(0) + 0번째 계단을 한번 오르는 수(1) = 1

2번째 계단을 오르는 수는 0번째 계단을 한번에 두번 오르는 수(1) + 1번째 계단을 한번 오르는 수(1) = 2

3번째 계단을 오르는 수는 1번째 계단을 한번에 두번 오르는 수(1) + 2번째 계단을 한번 오르는 수(2) = 3

4 : 2 + 3 = 5

5 : 3 + 5 = 8

...

처럼 직접 계산해보면서 확인할 수 있다.

 

차례차례 증가하는 경우는 그 전 결과를 사용할 수 있는지 생각하면서 알고리즘을 생각하면 좋다는 것을 배웠다.

# CodeUp 2632 : 계단 오르기 1
# n번 = n-1번 계단을 한번 오르는 수 + n-2번 계단을 두번 오르는 수이다.

n = int(input())

history_climb = []

def cnt_climb_set(cnt, history_climb) : #{
    if cnt == n : #{
      print(sum(history_climb))
      return

    else : #{
        cnt_climb_set(cnt+1, [history_climb[1], sum(history_climb)])
    #} 
#}

cnt_climb_set(1, [0, 1])