[백준] 11057 - 오르막 수

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

풀이

먼저 예제에서 나오는 결과들이 딱딱 맞아 떨어지는 것을 보고 생각보다 많이 간단한 패턴이겠구나라는 생각이 들었다. 먼저 N에 따라서 나오는 숫자들을 나열하여 찾은 패턴은 이렇다.

끝자리가 0인 숫자로부터는 0 ~ 9를 이어붙여 10개의 새로운 숫자들을 만들 수 있고, 끝자리가 1이라면 1 ~ 9를 이어붙여 그보다 한개 적은 9개의 새로운 숫자들, 끝자리가 2라면 8개 ... 이런식으로 끝자리가 하나 올라갈수록 해당 숫자로부터 만들어 질수 있는 새로운 숫자들은 1씩 줄어든다는 것을 알 수 있다.

따라서 첫번째 배열에는 1씩 두번째 배열에는 10부터 1까지의 숫자를 삽입한 후 N = 3부터는 이 식을 사용한다.

끝자리수가 9일 경우 = 만들어질 수 있는 숫자는 단 하나이므로 1

끝자리수가 9가 아닐 경우 = 자릿수가 하나 낮았을 때의 현재 끝자리수로 나왔던 조합의 수 + 현재 자릿수에서 끝자리수가 하나 더 높을 때 나오는 조합의 수

코드

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1001][10];

int main()
{
    cin.tie(NULL);
	ios_base::sync_with_stdio(false);
    int n, temp;
    long long ans = 0;
    /*
    n = 1: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 == 10
    n = 2: 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 11, 12, 13, 14, 15, 16 ... == 55
    n = 3: 000, 001, 002, 003, 004, 005, 006, 007, 008, 009, 011, 012, 013, 014 ... == 220

    수의 길이가 늘어날때마다 끝나는 자리 숫자에 따라 가능한 숫자 수가 다르다.
    예를들어 끝자리가 0이라면 0~9까지 10개의 새로운 숫자가 만들어질 수 있지만,
    끝자리가 9일 경우 9가 붙은 숫자 하나밖에 새로 만들어지지 않는다.

    n = 2일때는 0에 10, 1에 9, 2에 8 ... 9에 1 같은 식으로 되기 때문에 1 부터 10까지 더해서 55가 된다.
    n = 3일때는 00에 10, 01에 9 ... 09에 1, 그리고 11에 9, 12에 8 ... 19에 1 같은 식으로 이전 배열을 더해서 된다.
    */

    cin >> n;

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

    // n = 2
    for (int i = 0; i < 10; i++) {
        dp[2][i] = 10 - i;
    }

    // n >= 3
    for (int i = 3; i <= n; i++) {
        for (int j = 9; j >= 0; j--) {
            if (j == 9) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j+1];
            }

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

    for (int i = 0; i < 10; i++) {
        ans += dp[n][i];
    }

    ans %= 10007;

    cout << ans;

    return 0;
}