[ 백준 10844 ] 쉬운 계단 수 (C++)

백준의 쉬운계단수(10844) 문제이다.

( 문제 바로가기 )

[ 문제를 다시 푸는 과정에서 보다 구체적인 설명을 해 놓은 글을 다시 포스팅 하였습니다.

  아래의 글을 읽더라도 무관하지만 , 보다 구체적인 설명을 원하시는 분은 아래의 링크를 타고 글을 보시는 것을

  권장드립니다.

  ( 백준 쉬운계단수(10844) 풀이 바로가기 ) ]

[ 문제설명 ]

- 12321과 같이 모든 자리수의 차이가 1인 숫자를 계단 수 라고 한다.

- 입력으로 정수가 주어지고, 길이가 입력으로 주어진 정수인 계단 수가 몇 개인지 구하는 것이다.

- 0으로 시작하는 숫자는 없다고 가정하고 구현한다.

[ 문제풀이 ]

1) 먼저 나는 자릿수의 갯수를 저장할 2차원 배열 DP[][]를 사용했다.

2) DP[a][b] = 길이가 a 일 때 마지막 수가 b일 경우의 계단의 수를 의미한다.

3) DP[1][x] 의 경우 x에 어떤 값이 오더라도 1이 될것이다.

   왜냐하면, 한 자리 숫자는 1~9 모두 계단 수 이기 때문이다. 그리고 이식을 초기식으로 사용한다.

4) 2)같은 식을 생각해본 이유는 2자리 숫자를 만들 때, 중요한 것은 첫 째자리(마지막 수) 수이기 떄문이다.

   예를 들어, 2자리 숫자 중 앞에 자리를 1로 선택했다고 해보자.

   그렇다면 나올 수 있는 두자리 수는 10, 12 이다. 5로 선택했다고 가정하면 54, 56이 될것이다.

   3자리를 만드는데 앞에 2자리 중 마지막 자리 숫자에 따라서 가장 마지막 자리에 올 수 있는 숫자가

   결정될 수 있는 것이다. 예를들어 10, 34, 56, 89 라는 숫자인 상태에서 숫자 하나를 추가해서 3자리를 만든다고 

   생각해보자.

   10의 경우 2자리 중 마지막 자리 숫자인 0에 의해서 뒤에 올 수 있는 숫자는 1 하나 뿐이고

   34의 경우 2자리 중 마지막 자리 숫자인 4에 의해서 뒤에 올 수 있는 숫자는 3과 5 두개가 된다.

   56의 경우 5와 7이 있고, 9의 경우 8이 올 수 있다.

   즉, 만들어 놓은 수의 마지막 숫자에 의해서 그 다음에 올 수 있는 숫자들의 경우의 수가 정해지게 된다,

   하지만, 모든 경우의 수가 같은 것은 아니다. 위에서 말했다 시피 마지막 자리가 0과 9인 경우에는 경우의 수가 한개이고

   나머지 숫자들에 대해서는 2개의 경우가 성립하게 된다.

5) 3)에서 말한 초기식을 기반으로 점화식을 생각해보면

   2자리를 만드는 경우, 끝자리가 0으로 오는 경우의 수는(DP[2][0]) 10 한개 이다.

   2자리를 만드는 경우, 끝자리가 4로 오는 경우의 수는(DP[2][4]) 34, 54 2개 이다.

   2자리를 만드는 경우, 끝자리가 6으로 오는 경우의 수는(DP[2][6]) 56,76 2개이다.

   3자리를 만드는 경우, 끝자리가 5로 오는 경우의 수는(DP[3][5]) DP[2][4] + DP[2][6]가 된다.

   즉 점화식은 DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]이 된다.

   하지만, 마지막 자리가 0과 9인 경우에 대해서는 2가지가 아닌 한 가지 경우이므로 이 부분만 따로 조건을 걸어줘야 한다.

6) 또한 최대 자릿수가 100자리가 넘기 때문에 int형의 범위를 초과하니, 변수 선언할 때 자료형에도 신경을 써줘야 한다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 100 + 1
#define Moduler 1000000000
typedef long long ll;
using namespace std;
 
int N;
ll Answer;
ll DP[MAX][11];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    //DP[a][b] == 길이가 a 일때 마지막 수가 b일 경우의 계단의 수
    for (int i = 1; i <= 9; i++)
    {
        DP[1][i] = 1;    // 0을 제외한 한자리 숫자는 모두 계단 수 
    }
    DP[1][0] = 0;
 
    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] % Moduler;
            else if (j == 9) DP[i][j] = DP[i - 1][j - 1] % Moduler;
            else DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % Moduler;
        }
    }
 
    for (int i = 0; i < 10; i++)
    {
        Answer = Answer + DP[N][i];
    }
    cout << Answer % 1000000000 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}