[재귀] upstair

프로그램 명: upstair

제한시간: 1 초

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

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

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

입력

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

출력

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

입출력 예

입력

4

출력

5

#include <stdio.h>
 
#define MAX 31
 
int Num;
int stack[MAX];
int Count;
 
void input()
{
    scanf("%d", &Num);
}
 
void dfs(int depth, int value)
{
    int i;
    
    if(value == Num)
    {
        /*for(i=1; i<=depth; i++)
        {
            printf("%d ", stack[i]);
        }
        printf("\n");*/
        Count++;
        return;
    }
    else if(value > Num)
        return;
 
    stack[depth+1] = value+1;
    dfs(depth+1, value+1);
 
    stack[depth+1] = value+2;
    dfs(depth+1, value+2);
}
 
 
int main(void)
{
    input();
    dfs(0, 0);
    printf("%d\n", Count);
    return 0;
}