[백준,c++] 1174번 - 줄어드는 수

문제

1174번: 줄어드는 수

 

코드

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

int N;
string num = "0123456789";
vector<ll> asc;

void backtracking(int idx, string temp){
    
    if(!temp.empty()){
        string _temp = temp;
        reverse(_temp.begin(),_temp.end());
        asc.push_back(stoll(_temp));
    }
    
    for(int i=idx+1; i<10; i++){
        temp += num[i];
        backtracking(i, temp);
        temp.pop_back();
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    
    for(int i=0; i<10; i++){
        string temp = "";
        backtracking(i,temp+=num[i]);
    }
    
    sort(asc.begin(), asc.end());
    
    if(N>asc.size()) cout<<-1;
    else cout<<asc[N-1];
    
}

 

풀이

전형적인 백트랙킹 문제였습니다.

줄어드는 모든 수를 배열에 저장해놓고 마지막에 해당 순번에 해당하는 수를 출력하는 방식으로 해결했습니다. 

줄어드는 방식으로 하자니 보기가 불편해 증가하는 수열로 만들어가면서 배열에 넣을 때는 reverse 시켜서 최종적으로 줄어드는 수들을 넣었습니다.