백준 10844 쉬운 계단 수

문제

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

10844번: 쉬운 계단 수

 

인접한 자리의 차이가 1이 나는 수를 계단 수라고 한다.

ex) 1234567, 1212345, 345676567 ...

 

길이가  N인 계단수의 개수를 출력해야하는 문제로,

• N = 1  : 1, 2, 3, 4, 5, 6, 7, 8, 9 ..
• N = 2 : 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67 ..

계단 수를 보면 다음과 같은 점화식을 도출 할 수 있다.

D[ N ][ L ] = D[ N - 1 ][ L - 1 ] + D[ N - 1 ][ L + 1 ]

=> D[ 길이가 N인 계단 수 ][ 마지막으로 사용한 수 ] = D[ 길이가 N인 계단 수 - 1 ][ 마지막으로 사용한 수 - 1 ] + D[ 길이가 N인 계단 수 - 1 ][ 마지막으로 사용한 수 + 1 ]

 

마지막 L이 0 인경우와 L 이 9인 경우는 예외처리를 해주어야한다.

 

코드

#include <iostream>

using namespace std;

typedef long long ll;

int n;
ll ans, dp[101][11];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);                                                                                                                                                                 

    cin >> n;
    dp[1][0] = 0;
    for(int i = 1; i <= 9; i++)
        dp[1][i] = 1;

    for(int i = 2; i <= n; i++)
    {
        for(int j = 0; j <= 9; j++)
        {
            if(j == 0)
                dp[i][j] = dp[i-1][j+1] % 1000000000;
            else if(j == 9)
                dp[i][j] = dp[i-1][j-1] % 1000000000;
            else
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
        }
    }

    for (int i = 0; i < 10; i++)
        ans = ans + dp[n][i];

    cout << ans % 1000000000;

    return 0;
}