[BAE/<JOON> 문제풀이] 1038. 감소하는 수

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

1038번: 감소하는 수

최댓값을 987654321로 생각하고 풀었다.

 

아무리 해도 안되길래 질문 내용보고 9876543210 인걸 알았다.

 

능지

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    if (n < 10) {
        cout << n;
        return 0;
    }    
    if (n == 1022) {
        cout << 9876543210;
        return 0;
    }
    if (n > 1021) {
        cout << -1;
        return 0;
    }    
    vector<vector<vector<int>>> dp;
    //[자릿수][시작하는수][숫자들(push)]    
    int cnt = 0;
    n -= 10;
    dp.resize(10);
    for (int i = 0; i <= 9; i++) {
        dp[0].resize(10);
        dp[0][i].push_back(i);
    }
    int mask = 1;
    for (int i = 1; ; i++) {
        mask *= 10;
        for (int j = 1; j <= 9; j++) {          
            dp[i].resize(11);            
            for (int k = 0; k < j; k++) {                
                for (auto d : dp[i - 1][k]) {
                    dp[i][j].push_back(j * mask + d);
                    //cout << cnt << " " << j * mask + d << "\n";
                    if (cnt++ == n) {
                        cout << j * mask + d;
                        return 0;
                    }
                }
            }
        }
    }    
    return 0;
}