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

1. 문제 주소

 

10844번: 쉬운 계단 수

2. 문제

자릿수 N이 주어질 때 인접한 모든 자릿수의 차이가 1이 되는 경우의 수를 구하는 문제이다. 2차원 배열(d[n][1의 자릿수의 숫자])을 이용하여 코드를 작성하였다. 

n=1일 때 d[1][1]~d[1][9]까지 전부 1개씩 존재한다(0으로 시작하지 않으므로 d[1][0]=0).

n>=2일 때 d[n][0]은 d[n-1][1]에서 1개가 나오고, d[n][9]은 d[n-1][8]에서 1개가 나온다.

이 외에 모든 d[n][j]는 d[n][j-1]과 d[n][j+1] 1개씩 나오게 된다. 이를 이용하여 코드를 작성하였다.

3. 소스 코드

#include <iostream>
using namespace std;
 
long long d[101][10];
long long num = 1000000000ll;
 
int main(void)
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            if (i == 1)
            {
                if (j >= 1)
                    d[i][j] += 1;
            }
            else
            {
                if (j == 0)
                    d[i][j] += d[i - 1][j + 1] % num;
                else if (j == 9)
                    d[i][j] += d[i - 1][j - 1] % num;
                else
                    d[i][j] += (d[i - 1][j - 1] + d[i - 1][j + 1]) % num;
            }
        }
    }
    long long result = 0;
    for (int j = 0; j <= 9; j++)
        result += d[n][j] % num;
 
    cout << result % num << '\n';
    return 0;
}