코드업(codeup) 2641 : 숏다리의 계단 오르기 (Small) C언어

▶문제 : 숏다리의 계단 오르기 (Small) (codeup.kr)

숏다리의 계단 오르기 (Small)

 

▶코드 작성

#include <stdio.h>

int cnt;//경우의 수
int N;//입력 값

void fuc(int n, int t)
{
    if (t > 0) t--;//3계단을 올랐을 때 두 번 턴을 셀 때 사용
    if (N == n) cnt++;
    else if (N > n)//N보다 n이 작을 때
    {
        if (t == 0) fuc(n + 3, 3);//3계단을 오를 때 t=3을 하여 턴을 준다.
        fuc(n + 2, t);//두 칸 오를 때
        fuc(n + 1, t);//한 칸 오를 때
    }
}

int main()
{
    scanf("%d", &N);
    fuc(0, 0);
    printf("%d", cnt);

    return 0;
}

 

▶해석

재귀 함수를 이용하여 1칸, 2칸, 3칸 각각 오르도록 하였다. 3칸을 올랐을 때 t값에 3을 추가하여 두 턴을 쉴 수 있게 하였고, 턴을 세기 위해 함수가 호출될 때마다 t--을 해주었다.