N 개의 계단

문제

N 개의 계단을 사람이 오른다고 하자.

한 번에 1계단 오르기도 하고, 2계단이나 3계단씩 오르기도 한다.

계단을 오르는데 몇 가지 방법이 있는가?

 

문제 분석

N 번째 계단에 도달하는 방법을 생각해보자.

N - 1 번째 계단에서 한 계단 더 올라 N 번째 계단에 도달했을 수도 있고,

N - 2 번째 계단에서 두 계단을 뛰어 N 번째 계단에 도달했을 수도 있고,

N - 3 번째 계단에서 세 계단을 한 번에 뛰어 N 번째 계단에 도달했을 수도 있다.

그러므로,

마지막 계단에 오르는 방법의 가짓수는 그 전 세 계단에 도착하는 경우의 수를 전부 더한 것이다.

 

구현

프로그램 실행결과

 

소스 파일

main.c

0.00MB