[백준][10844번][DP] 쉬운 계단 수

쉬운 계단 수

https://www.acmicpc.net/problem/10844

<코드>

#include <stdio.h>
#define mod 1000000000
int main(void){
    int N;
    int Dp[101][10] = {};
    int sum = 0;
    scanf("%d", &N);
    for (int i = 0; i < 10; i++)
        Dp[1][i] = 1;
    for (int i = 2; i <= N; i++){
        for (int j = 0; j < 10; j++){
            if (j == 0)
                Dp[i][0] = Dp[i - 1][1] % mod;
            else if (j == 9)
                Dp[i][9] = Dp[i - 1][8] % mod;
            else
                Dp[i][j] = (Dp[i - 1][j - 1] + Dp[i - 1][j + 1]) % mod;
        }
    }
    for (int i = 1; i < 10; i++)
        sum = (sum + Dp[N][i]) % mod;
    printf("%d\n", sum%mod);
}

<문제 푼 요령>

1. 자릿수가 증가함에 따라서 경우의 수도 증가하는데 이 증가할때 법칙이 있다.

2. 이 법칙은 j 자릿수 i 수에 대해서 j-1 자릿수의 i-1과 i+1을 더한 수가 i 수에 대한 값이 되는것이다. 예를들면

 -  1 ,2 ,3 ,4 ,5 가 있다고 하면 10 자리수의 쉬운 계단 수를 만들려고 앞의 자리를 1로 결정하는 순간 뒤의 자리수는 0 아니면 2 가 된다. 

 - 10 ,12, 21, 23, 32, 34 에서 100의 자리수의 쉬운 계단 수를 만들려고하는데 앞자리가 2라면 그 뒤에 10 ,12, 32, 34 의 수가 될 수 있다. 

3. 즉 이전 자리수의 앞자리 수의 경우의 수만 알면 지금 자리수에 경우의 수를 구할 수 있게 되는것이다.

4. 이 것을 주욱 반복하면 정답을 구할 수 있다.