[백준,c++] 1038번 - 감소하는 수

문제

1038번: 감소하는 수

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;


vector<ll> v;

void backtracking(string s){
    if(s > "9876543210") return;
    string temp = s;
    reverse(temp.begin(), temp.end());
    v.push_back(stoll(temp));
    for(int i=s.back() - '0' + 1; i<=9; i++){
        string num = to_string(i);
        backtracking(s + num);
    }
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin>>n;
    for(int i=0; i<=9; i++){
        string num = to_string(i);
        backtracking(num);
    }
    sort(v.begin(), v.end());
    
    if(n>=v.size()) cout<<-1;
    else cout<<v[n];
}

 

풀이

1. 0, 01, 012, 0123...., 0123456789, 012345679, 01234568, 012345689 ... 순으로 증가하는 순으로 backtracking을 탐색합니다.
2. 위 number를 거꾸로 즉 역순으로 바꾸면 감소하는 수가 되기에 reverse 시켜서 vector에 저장합니다.
3. 가장 큰 감소하는 수는 9876543210 으로 int값을 넘기 때문에 long long으로 vector를 선언해줍니다.
4. 마지막에 정렬 후 찾고자 하는 N을 V[N]으로 출력하면 됩니다.

총 v[0] = 0, .... v[1022] = 9876543210이 됩니다.