코드업(codeup) 3802 : 쉬운 계단 수 C언어

▶문제 : 쉬운 계단 수 (codeup.kr)

쉬운 계단 수

 

▶코드 작성

#include <stdio.h>

int arr[101][10];//자리수, 0 ~ 9 숫자 => 메모이제이션

void func(int d, int n)
{
    for (int i = d - 1; i <= d + 1 && n > 1; i += 2)//d에서 -1 또는 +1이 되야 하므로
    {
        if (i < 0) continue;//i=-1이 나올 수 없도록
        if (i > 9) break;//i=10이 나올 수 없도록
        if (arr[n - 1][i] == 0) func(i, n - 1);
        //n자리수의 다음 n-1자리수가 저장되지 않았을 때 재귀 호출
        arr[n][d] = (arr[n][d] + arr[n - 1][i]) % 1000000000;//n-1자리수의 i값을 더함
    }
}

int main()
{
    int n;
    int cnt = 0;
    scanf("%d", &n);

    for (int i = 0; i <= 9; i++) arr[1][i] = 1;//일의 자리수는 1

    for (int i = 1; i <= 9; i++)//앞자리는 0이 될 수 없음 => 1 ~ 9
    {
        func(i, n);
        cnt = (cnt + arr[n][i]) % 1000000000;
    }
    
    printf("%d", cnt);
    return 0;
}

 

▶해석

첫째 자리 수는 0 ~ 9 모두 1이므로 대입한다.

앞자리 수는 0이 될 수 없으므로 1부터 9까지 반복한다.

앞자리가 1일 때부터 시작하므로 func(1, n)가 된다.

d=1이므로 다음 자리는 0 또는 2가 되어야 한다.

for문으로 0부터 시작해 arr [n-1][0]이 있는지 확인한다.

없으면 재귀 함수를 통해 arr [n-1][0] 값을 구하기 위해 func(0, n-1)를 호출해 값을 구한다.

있으면 arr [n][1]에 0일 때의 값을 더하고 다음 2일 때의 값 또한 더해준다.

그렇게 arr[n][1] ~ arr [n][9]의 값을 구해서 cnt에 더해준다.