[구름]계단 오르기

링크 : https://level.goorm.io/exam/43083/%EA%B3%84%EB%8B%A8-%EC%98%A4%EB%A5%B4%EA%B8%B0/quiz/1

구름LEVEL

우선 문제를 분석해 보겠습니다. 계단을 최대 2칸 오를 수 있다고 할때 계단을 오르는 방법의 가짓수를 출력하는 프로그램을 작성하시오.

n 이 3인경우

 

1. 1 - 2 - 3

2. 1 - 3

3. 2 - 3

 

이를 기반으로 그림으로 작성해 보면 아래와 같습니다.

내가 지은 결론은, 계단을 계속해서 오르다고 2칸이 남는다고 한다면 2칸 모두 가거나, 1칸씩 2번가거나 총 2번의 경우의 수가 생긴다. 반면, 1칸이 남는다고 한다면 1칸만 가면 된다. 종료조건을 확실하게 하기 위해서 아래와 같이 생각했다

 

- 1칸이 남는다면 : 확실한 종료조건이므로, count + 1

- 2칸이 남는다면 : 1칸씩 두번 올라가게 되면, 위 조건에 의해 필터링된다. 만약 2칸을 오르게 되면 남는 칸수는 0이 되고, 이는 확실한 종료조건이 된다. 

 

한가지 더 고려해야할 조건은, 시작을 하는것인데, 최대 2칸올라갈 수 있으므로, 1칸 올라가는 시작 한개, 2칸 올라가는 시작 한개로 재귀함수를 작성해 준다. 코드는 아래와 같다.

 

def solve(n)-> int:
    if n == 0 or n == 1:
        return 1
    return solve(n - 1) + solve(n-2)


if __name__ == "__main__":
	inp = int(input())
	print(solve(inp))