4.4.1

main.py

"""
문제 4.4 계단 오르기

입력으로 주어지는 n개의 계단을 1번에 1개 혹은 2개 올라 도달할 수 있는 방법의 가짓수를
찾아내는 문제이다. 예를 들어서, N이 3으로 주어지면

1. 1 + 1 + 1 = 3
2. 1 + 2 = 3
3. 2 + 1 = 3

위의 결과와 같이 1번에 1개 혹은 2개의 계단을 올랐을 때, n개 까지 도달할 수 있는 방법을 조사하는 것이다.

## 제한 사항

1. 입력 숫자는 양의 정수 이다.

## 아이디어(재귀)

- 계단을 오를 때, 1번 오르거나 2번 오를 수 있다.
- 1번 오를지 2번 오를지 재귀적으로 모든 경우를 탐색 한다.
- 그리고 나서, 오르려는 계단과 같다면 1을 오르려는 계단보다 많이 오른 경우는 0을 리턴한다.

"""


def climbStarts(n: int) -> int:
    def climb(n, i):
        if n == i:
            return 1
        if n < i:
            return 0
        return climb(n, i + 1) + climb(n, i + 2)
    return climb(n, 0)


if __name__ == '__main__':
    n = int(input())
    print(climbStarts(n))