백준 10844 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

 

 

EXPLANATION

 

길이가 i이면서 i자리의 수가 j인 계단 수의 갯수를 dp[i][j]라고 하자.

0자리 수는 없으므로 dp[i][j]에서 i는 1부터 시작한다.

j는 0~9에 속하므로 0부터 시작한다.

 

 

1)

dp[i][0] = dp[i-1][1]

길이가 i이면서 i자리의 수가 0인 계단 수는 i-1번째 자리의 수가 1일 때만 가능하기 때문이다.길이가 i이면서 i자리의 수가 0인 계단 수의 갯수는길이가 i-1이면서 i-1자리의 수가 1인 계단의 수의 갯수와 같다.ex) i=3, j=0일 때 012, 010총 2개

 

i=2, j=1일 때

12, 10

총 2개

 

 

2)

dp[i][9] = dp[i-1][8]

길이가 i이면서 i자리의 수가 9인 계단 수는 i-1번째 자리의 수가 8일 때만 가능하기 때문이다.

길이가 i이면서 i자리의 수가 9인 계단 수의 갯수는

길이가 i-1이면서 i-1자리의 수가 8인 계단의 수의 갯수와 같다.

ex)

i=3, j=9일 때

987, 989

총 2개

 

i=2, j=8일 때

87, 89

총 2개

 

 

3)

dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1])

길이가 i이면서 i자리의 수가 0, 9가 아닌 j인 계단 수는 i - 1번째 자리의 수가 j - 1이거나 j + 1일 때만 가능하기 때문에

길이가 i이면서 i자리의 수가 0, 9가 아닌 j의 갯수는

길이가 i-1이면서 i-1자리의 수가 j - 1 이거나 j + 1인 계단의 수의 갯수와 같다.

ex)

i=3, j=4일때

432, 434, 454, 456

총 4개

 

i=2, j=3 (4-1)일때

32, 34

총 2개

 

i=2, 1=5 (4+1)일때

54, 46

총 2개

 

 

주의할 점, N자리의 수는 십진수에서 0이 될 수 업기 때문에

N자리의 수의 모든 계단 수의 갯수를 구할 때

dp[N][0]은 빼고 dp[N][1]부터 dp[N][9]까지만 더한다.

 

 

 

base 구하기:

i가 1일 때 1자리 수이므로 각 j에 대해서 하나씩만 나온다.

즉, 어떤 j인지에 상관없이

dp[1][j] = 1

 

 

점화식

dp[1][j] = 1

dp[i][0] = dp[i-1][1]
dp[i][9] = dp[i-1][8]
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1])	//j!=0 && j!=9

 

 

CODE

#include <iostream>
using namespace std;
#define mod 1000000000

int main()
{

    int dp[101][10] = {};    //for[1,N][0,9]
    int n;
    int sum = 0;

    cin >> n;

    for (int j = 0; j < 10; j++)    //base
        dp[1][j] = 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];
            else if (j == 9)
                dp[i][9] = dp[i - 1][8];
            else
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]);
            dp[i][j] %= mod;
        }
    }
    for (int j = 1; j < 10; j++)     //N의 자리에는 '1'~9만 올 수 있음
        sum = (sum + dp[n][j]) % mod;

    cout << sum;
}