문제

영일(01)이는 n개의 계단을 오르려고 한다.

영일이는 다리가 짧아 계단을 오를 때 한 번에 1 계단 또는 2 계단만 오를 수 있다.

영일이가 n번째 계단에 도달할 수 있는 방법의 수를 구하시오.

입력

계단의 수 n이 입력된다.

입력 예시

3

출력

계단을 오를 수 있는 방법의 수를 출력한다.

출력 예시

3

문제 풀이

직접 세다보면 규칙을 찾아낼 수 있다.

n=1, 1
n=2,
1+1
2
n=3 > f(n-1)+f(n-2)
1 1 1 (n = 2) + 1
2 1 (n = 2) + 1
1 2 (n=1) + 2
n=4 > f(n-1) + f(n-2)
1 1 1 1 (n=3)+1
2 1 1 (n=3)+1
1 2 1 (n=3)+1
1 1 2 (n=2) + 2
2 2 (n=2)+2

# n 개의 계단 오르기, 1~2 만큼 움직일 수 있음

# 계단 수
n = int(input())

# f(n) = f(n-1) + f(n-2)
def Climbing(n):
    if n == 1 or n == 0 :
        return 1
    elif n > 1:
        return Climbing(n-1)+Climbing(n-2)

print(Climbing(n))