[Greedy / Gold5] 1038번: 감소하는 수

문제 출처

www.acmicpc.net/problem/1038

문제 내용

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

풀이

정수 X가 a 자리 수라고 했을 때, X가 감소하는 수가 되려면 a-1부터 1의 자리수까지 a보다 작은 감소하는 수로 이뤄져있어야 한다. 이러한 조건을 3차 배열로 나타냈다. 각 인덱스는 다음을 의미한다. arr[자리수][해당 자리의 숫자][순번]. 즉, arr[3][2][4]이면 천의 자리의 수가 2인 감소하는 수 중에서 4번째 수인 것이다. 

코드

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

typedef long long ll;

const int MAX_SIZE = 50;

vector<vector<vector<ll>>> memo;

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int N; cin >> N;
    int cur=0;
    ll ans = -1;
    
    memo = vector<vector<vector<ll>>> (MAX_SIZE, vector<vector<ll>>(10) );
    
    memo[1][0].push_back(0);
    for (int i = 1; i < 10; ++ i) {
        memo[1][i].push_back(i);
        ++ cur;
        if (N == cur) ans = i;
    }
    
    // memo[자리수][해당 자리의 숫자][순번]
    for (int i = 2; i < MAX_SIZE; ++ i) {
        for (int j = 1; j <= 9; ++ j) {
            for (int k = 0; k < j; ++ k) {
                for (int d = 0; d < memo[i-1][k].size(); ++ d) {
                    memo[i][j].push_back( pow(10, i-1) * j + memo[i-1][k][d]);
                    ++ cur;
                    // if (N >= cur) cout << cur << " " << memo[i][j][memo[i][j].size()-1] << endl;
                    if (N == cur) ans = memo[i][j][memo[i][j].size()-1];
                }
                    
            }
        }
    }
    
    if (N == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    cout << ans << endl;
    
    return 0;
}