백준 1038 감소하는 수

일단 나는 처음에 문제를 어떻게 풀어야 할 지 감을 잡기 위해 작은 자리수부터 차례대로 감소하는 수를 나열했다.
한 자리 : 0 1 2 3 4 5 6 7 8 9
두 자리 : 10 20 21 30 31 32 ... 97 98
세 자리 : 210 310 320 321 410 ... 987
이렇게 나열하다보니 개수의 패턴이 보였다.

자리수 / 첫번째 자리 숫자	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	0	1	2	3	4	5	6	7	8	9
3	0	0	1	3	6	10	15	21	28	36
...	.	.	.	.	.	.	.	.	.	.
10	0	0	0	0	0	0	0	0	0	1

• 표의 각 칸은 해당 자리수의 해당 첫번째 자리 수일 때 개수이다.
• 파스칼 삼각형이 얼핏 보인다.

첫번째 자리 수 = i라고 할 때,
i = 0일 때 $2^0$개
i = 1일 때 $2^1$개
...
i = 9일 때 $2^9$개이므로
$2^0 + 2^1 + ... + 2^9 = 2^{10}-1$ = 감소하는 수의 개수임을 알 수 있다.
따라서 나는 감소하는 수를 백트래킹으로 간단하게 구하고 정렬했다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
ll num = 0;
vector<ll> decNum;
void dfs(int k, int idx) {
    if (k == n) {
        decNum.push_back(num);
        return;
    }
    for (int i = idx; i >= 0; --i) {
        num = num * 10 + i;
        dfs(k+1, i-1);
        num /= 10;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    for (int i = 1; i <= 10; ++i) {
        n = i;
        dfs(0, 9);
    }
    sort(decNum.begin(), decNum.end());
    int x;
    cin >> x;
    if (x > 1022) cout << -1;
    else cout << decNum[x];
}

감소하는 수가 int 범위를 넘어서는 것만 주의하면 간단하게 문제를 해결할 수 있다.