[ 백준 11057 ] 오르막 수 (C++)

백준의 오르막수(11057) 문제이다.

( 문제 바로가기 )

[ 문제를 다시 풀어보는 과정에서 보다 보다 구체적인 설명으로 글을 다시 포스팅 하였습니다.

  아래의 글을 읽으시고 문제를 푸셔도 무관하지만, 보다 구체적인 설명을 원하시는 분들께서는

  아래의 링크를 이용해 주시면 감사하겠습니다.

   [ 백준 오르막수(11057) 풀이 바로가기 ] ]

[ 문제풀이 ]

1. 나는 먼저 오르막수를 관리하기 위해서 DP[][] 2차원 배열을 사용했다.

   DP[a][b]의 의미는 "a자리의 수에서 b가 가장 마지막에 왔을 때, 오르막수가 될 수 있는 경우의 수" 를 의미한다.

   예를 들어서 설명해 보겠다. DP[2][3]의 경우 총 자릿수가 2자리인데, 그 중에서 마지막에 3이 왔을 때 오르막 수가 될 수 있는

   경우의 수를 의미한다. 즉, _3 이 경우인 것이다.

2. 그렇다면 DP[1][a]는 얼마일까? 위의 말을 토대로 그대로 해석해보자면, 한 자리 수에서 a라는 숫자가 가장 마지막에

   왔을 때, 오르막 수가 될 수 있는 경우의수? 무조건 1가지 일 것이다.

   예를들어서 a가 1인 경우, DP[1][a]가 의미하는 숫자는 1일 것이고, 이건 한 가지 경우 뿐이기 때문이다.

   즉 DP[1][a] (0 <= a <= 9) 는 1이 될 것이다.

3. 그렇다면, 더 나아가서 DP[3][4]의 값을 한번 계산해보자.

   DP[3][4]는 3자리의 숫자에서 4가 가장 마지막 자리에 왔을 때, 오르막 수가 될 수 있는 경우의 수를 의미한다.

   즉, ? ? 4 이렇게 됬을 때 경우의 수를 구하면 된다.

   그렇다면 a b 4 라고 생각하고 접근해보자. 먼저 b에 올 수 있는 숫자는 무엇이 있을까??

   아마 오르막수가 되기위해서 b = 0, 1, 2, 3, 4가 올 수 있을 것이다.

   b가 0인 경우 a는 0

   b가 1인 경우 a는 0 1

   b가 2인 경우 a는 0 1 2

   b가 3인 경우 a는 0 1 2 3

   b가 4인 경우 a는 0 1 2 3 4 가 올 수 있다.

   그렇다면 위의말을 한번 식으로 만들어보자. 먼저 b의 값은 우리가 어떻게 구했을까?

   b에 올 수 있는 (0, 1, 2, 3, 4) 라는 5가지 경우는 아마 DP[2][4]의 결과와 같을 것이다.

   " DP[3][4]의 결과를 알아내기 위해서, DP[2][4]의 결과값이 사용되구나 " 라는 것 정도만 알고 다음 단계로 넘어가보자.

   그렇다면 DP[2][4]는 어떨까????

   DP[2][4] = DP[1][0] + DP[1][1] + DP[1][2] + DP[1][3] + DP[1][4]

   위의 식을 한번 설명해보겠다.

   2자리 숫자 중에서 가장 마지막 숫자가 4일 때, 오르막 수가 될 수 있는 경우는

   1자리 숫자 중에서 [0이 오는 경우] + [1이 오는 경우] + [2가 오는 경우] + [3이 오는 경우] + [4가 오는 경우] 입니다.

    이 과정을 위해서 처음에 말한 DP[1][a]의 값이 필요한 것이다.

    그런데 문제는 이게 아니다. 문제는 보면, N이라는 값이 주어지면, N자릿수인 오르막수의 갯수를 구하는 것이다.

    즉, 위의 풀이처럼 전체 자릿수가 2자릿수이고, 가장 마지막 숫자가 4일 때, 오르막수의 갯수를 구해라 이게 아니라는 것이다.

    즉, N자릿수인 오르막 수를 구하기 위해서는 가장 마지막 숫자가 0일 때부터 9까지 모든 경우를 다해서 다 더해줘야

    할 것이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1001
#define Moduler 10007
using namespace std;
 
int N;
int DP[MAX][10];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    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++)
        {
            for (int k = 0; k <= j; k++)
            {
                DP[i][j] = DP[i][j] + DP[i - 1][k];
                DP[i][j] = DP[i][j] % Moduler;
            }
        }
    }
 
    int Answer = 0;
    for (int i = 0; i < 10; i++)
    {
        Answer = Answer + DP[N][i];
    }
    Answer = Answer % Moduler;
 
    cout << Answer << 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;
}