[BOJ 10844] 쉬운 계단 수

문제 출저 : https://www.acmicpc.net/problem/10844

 

풀이 :

 

DP문제입니다.

0으로 시작 하는 수는 없지만 0으로 끝나는 수는있음에 주의합시다.

이 문제도 [11057] 오르막 수 이 문제와 마찬가지로 (현재 자릿수 - 1)의 값을 이용하여 데이터를 쌓습니다.

마지막 수가 0일때와 9일때는 각 각 그 전자리 수가 1, 8일때만 계단수가 되므로 따로 계산을 해줍니다.

나머지 1~8일때는 각 각 (자신 - 1), (자신 + 1)의 값을 들고 오면 되므로 for문으로 따로 계산을 해주시면 됩니다.

 

#include<stdio.h>
 
int n,cache[101][10],ret,mod=1000000000;
 
int main()
{
    scanf("%d", &n);
    for (int i = 1; i < 10; i++)cache[1][i] = 1;
    for (int i = 2; i <= n; i++)
    {
        cache[i][0] = cache[i - 1][1];
        cache[i][9] = cache[i - 1][8];
        for (int j = 1; j < 9; j++)
        {
            cache[i][j] = (cache[i - 1][j - 1] + cache[i - 1][j + 1])%mod;
            if (i == n)ret = (ret + cache[i][j])%mod;
        }
    }
    printf("%d", n == 1 ? 9 : ((ret + cache[n][0])%mod+cache[n][9])%mod);
}