[알고리즘 문제] 백준11057 - 오르막 수

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

11057번: 오르막 수

길이가 N일 때의 오르막 수의 개수를 구하는 문제 입니다. 오르막 수란 숫자가 오름차순으로 되어있는 숫자를 말합니다. 예를 들어 15679은 오르막수 이지만 15267은 오르막수가 아닙니다. 

 

길이가 3이고 숫자의 가장 오른쪽 숫자가4인 경우를 한번 보겠습니다. 여기서는 이를 [3,4]으로 표현합니다.

[3,4]인 경우 _ _ 4으로 표현할 수 있습니다. 어쨋든 가장 오른쪽 숫자4는 고정되어 있습니다. 그렇다면 앞의 2자리에 총 몇개의 오르막 수가 올 수 있는지 구하면 답을 알 수 있겠네요.

 

문제의 이해를 돕자면 [1,2,3,4]의 순열을 구할 때 제일 1로 시작하는 순열을 구해보면 (n-1)!입니다. 천의자리 1은 고정이기 때문에 고려하지 않고, 이후의 백의 자리부터 순열을 구하면 되죠.

 

오르막수도 비슷한 논리입니다. 제일 오른쪽수 4가 고정되어 있기 때문에 앞의 2자리의 오르막수(순열(?))을 구하면 되죠. 인접한 수가 같아도 오름차순이기 때문에 4도 포함입니다.

 

다시 문제에서 _ _ 4일때 앞의 2자리를 구하는 방법을 생각해 봅시다. 이는 _0, _1, _2, _3, _4인 오르막수를 구해야 합니다. 각 2자리 끝에 4를 붙이면 [3,4]를 만족하겠죠. 아래의 사진을 보고 이런 같은 논리가 유효한지 한번 알아 봅시다.

 



길이가 i이고 가장 오른쪽 숫자가j의 오르막 수의 개수는 dp[i][j]에 저장되며 ,점화식은 dp[i][j] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2].... dp[i-1][j]가 됩니다.

 

원래 dp[i][j]값을 구하기 위해서는 형광칠한 부분과 작은원의 값을 반복물을 사용해서 다 구해야 하지만, 사실상 형광칠한 부분은 15의 바로 왼쪽에 저장되어 있습니다. 그렇기 때문에 코드상에는 dp[i][j] = dp[i-1][j] + dp[i][j-1]을 사용했습니다.

 

예외처리는  제일 왼쪽에 있는 값은 따로 더할 값이 없기 때문에 바로 위의 값을 이어 받고, dp에 저장되는 값은 10007로 나눈 나머지 값을 저장합니다.

#include <iostream>

using namespace std;

int main()
{

    int dp[1001][10];
    int mod = 10007;

    int n;
    cin >> n;

    for (int i = 0; i <= 9; i++)
    {
        dp[1][i] = 1;
    }

    for (int i = 2; i <= n; i++) // i : 숫자의 길이
    {
        for (int j = 0; j <= 9; j++) // j : 숫자에서 제일 오른쪽값
        {
            if (j == 0)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

            dp[i][j] %= mod;
        }
    }

    for (int i = 2; i <= n; i++) // i : 숫자의 길이
    {
        for (int j = 0; j <= 9; j++) // j : 숫자에서 제일 오른쪽값
        {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }

    int result = 0;
    for (int i = 0; i <= 9; i++)
    {
        result = (result + dp[n][i]) % mod;
    }

    cout << result;

    return 0;
}