백준 1174 - 줄어드는 수

문제링크 : https://www.acmicpc.net/problem/1174
알고리즘 종류 : 백트래킹
솔? : 보고 함
핵심 아이디어 : 줄어드는 수의 특성을 잘 생각해서 풀어야함

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

int N;
string num = "0123456789";
vector<long long> correct;

void backtracking(int idx, string temp) {

    if (!temp.empty()) {
        string _temp = temp;
        reverse(_temp.begin(), _temp.end());
        correct.push_back(stoll(_temp));
    }

    for (int i = idx + 1; i < 10; i++) {
        temp += num[i];
        backtracking(i, temp);
        temp.pop_back();
    }
}

int main() {
    scanf("%d", &N);

    for (int i = 0; i < 10; i++) {
        string temp = "";
        backtracking(i, temp += num[i]);
    }

    sort(correct.begin(), correct.end());

    if (N > correct.size()) {
        printf("%d", -1);
    }
    else { 
        cout << correct[N - 1];
    }

}

후기 : 하.. 이런 생각을 어떻게 하지?

잘설명된 링크 (이건 거의 배꼈음..): https://dkswnkk.tistory.com/607