감소하는 수 C++ - 백준 1038

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

백트래킹 문제.

stoi를 사용해서 오류가 났었다.

stoll(string to long long)을 알게된 문제.

문제 접근

감소하는 수를 순서대로 백트래킹 하기 어렵기 때문에,

예제에서 50000번째 이상은 감소하는 수가 없는 것을 보았기 때문에,

모든 감소하는 수를 구하고 정렬한 뒤 순서에 맞는 감소하는 수를

출력하도록 했다.

백트래킹을 할 때 자신보다 작으면 여태까지의 string s에 그 값을

추가해 백트래킹 해주었다.

코드는 다음과 같다.

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

int n;
vector<long long> v;

void dfs(string s){
    int x=s[s.length()-1]-'0';
    v.push_back(stoll(s));
    for(int i=0;i<10;i++){
        if(x<=i) break;
        dfs(s+to_string(i));
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i=0;i<10;i++) dfs(to_string(i));
    sort(v.begin(),v.end());
    if(v.size()<n+1) cout << -1;
    else cout << v[n];
    return 0;
}