쉬운 계단 수 _ 백준 10844

10844

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

계단 수 : 인접한 모든 자리수의 차이가 1인 수.

 

여기서 d[n] = 길이가 N인 계단 수의 개수라고 볼 수 있지만, 여기서 우리는 인접한 수의 차이가 1 인것도 고려해야 한다.

 

그렇다면 마지막 숫자를 배열에 추가하여 d[n][i] = 길이가 n인 계단 수이며, 마지막 숫자가 i인것으로 하여 점화식을 세우면 된다.

처음에 잘못생각해서, 마지막 숫자가 아니라 첫번째 숫자로 생각했더니 문제가 발생했기 때문에... 마지막 숫자라는 것을 유의했으면 좋겠다.

 

따라서 점화식을 세우면 d[n][i] = d[n-1][i-1] + d[n-1][i+1]이다.

다만, i가 0, 9 일 때에는 d[n][0] = d[n-1][1], d[n][9] = d[n-1][8] 이라는 것에 주의하자.

 

이중 for문을 돌려서 해당 배열에 값을 넣으면 되는데, 0일때와 9일때를 구별하기 위해서 if 조건문을 추가하였다.

#include <stdio.h>
long long d[101][10];
#define MOD 1000000000

int main(void)
{
    int a;
    long long ans = 0;

    scanf("%d", &a);
    for (int i = 1; i < 10; i++)
        d[1][i] = 1;

    for (int i = 2; i <= a; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            d[i][j] = 0;
            if (j - 1 >= 0)
            {
                d[i][j] += d[i - 1][j - 1];
            }
            if (j + 1 <= 9)
            {
                d[i][j] += d[i - 1][j + 1];
            }
            d[i][j] %= MOD;
        }
    }
    for (int i = 0; i < 10; i++)
    {
        ans += d[a][i];
    }
    printf("%d", ans % MOD);
}