계단
-
N 개의 계단Algorithm with C/DFS 2020. 9. 16. 18:58
문제 N 개의 계단을 사람이 오른다고 하자. 한 번에 1계단 오르기도 하고, 2계단이나 3계단씩 오르기도 한다. 계단을 오르는데 몇 가지 방법이 있는가? 문제 분석 N 번째 계단에 도달하는 방법을 생각해보자. N - 1 번째 계단에서 한 계단 더 올라 N 번째 계단에 도달했을 수도 있고, N - 2 번째 계단에서 두 계단을 뛰어 N 번째 계단에 도달했을 수도 있고, N - 3 번째 계단에서 세 계단을 한 번에 뛰어 N 번째 계단에 도달했을 수도 있다. 그러므로, 마지막 계단에 오르는 방법의 가짓수는 그 전 세 계단에 도착하는 경우의 수를 전부 더한 것이다. 구현 프로그램 실행결과 소스 파일