[재귀] 계단 오르기

프로그램 명: upstair                                                                                                            제한시간: 1 초

최대 2 칸 까지 오를 수 있을 때 오르는 방법의 가짓수를 출력 하는 문제이다.

그림은 n 이 4 인 경우의 예 이다.

• 1 - 2 - 3 - 4
• 1 - 2 - 4
• 1 - 3 - 4
• 2 - 3 - 4
• 2 - 4

입력

n 은 30 이하의 양의 정수이다.

출력

오를 수 있는 가짓 수를 출력한다.

입출력 예

입력

4

출력

5

[문제 풀이]

최대 2칸을 오를 수 있다는 것은, 한 번에 1칸 또는 2칸을 올라갈 수 있다는 뜻이다.

• 1칸씩 올라가기 : 1 - 2 - 3 - 4
• 1칸 - 1칸 - 2칸 : 1 - 2 - 4
• 1칸 - 2칸 - 1칸 : 1 - 3 - 4
• 2칸 - 1칸 - 1칸 : 2 - 3 - 4
• 2칸씩 올라가기 : 2 - 4 

이렇게 입력받은 수(n)만큼 올라갈 수 있는 방법의 가짓 수를 출력하는 것이 목표이다.

[소스코드 설명]

stair()의 n은 목표 계단 높이, now는 현재 계단 높이를 말한다.

문제 풀이에서도 설명을 했듯이, 한 번에 1칸 또는 2칸을 올라갈 수 있다는 뜻이기 때문에 

1칸 올라가는 경우(stair(n, now + 1))와 2칸 올라가는 경우(stair(n, now + 2))를 모두 구해서

목표 계단 높이(n)과 같을 때까지 재귀 호출을 하였다.

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

#include <iostream>   using namespace std;   int stair(int n, int now) {     if (now == n)         return 1;     if (now > n)         return 0;     return stair(n, now + 1) + stair(n, now + 2); }   int main() {     int n;       cin >> n;       cout << stair(n, 0);       return 0; }