[BOJ/C++] 1174: 줄어드는 수

🥇 Gold 5

✏️ 최종 솔루션

⭐️ 백트래킹
⭐️ 가능한 숫자 0~9876543210 범위 내의 줄어드는 숫자를 모두 vector에 push 하고 n 번째 숫자 return

1. 0~9 까지 vector에 push
2. 1~9를 첫째 자리로 가지는 모든 수 vector 에 push
   ➡️ dfs 로 현재까지 완성한 숫자와 현재까지 추가된 숫자 전달
   ❗️ 편의상 만든 숫자는 문자열로 관리
   ❗️ 완성한 숫자는 long long 형으로 변환해
3. 현재 숫자보다 작은 숫자들만 이어서 추가
4. 모든 숫자를 추가한 이후에 n-1 번째 숫자 return

📌 self feedback

자릿수를 따져주는 문제는 문자열로 처리해주는 게 더 간편

✏️ 최종 code

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<long long> v;
void dfs(string s,int cur) {
    for(int i=cur-1;i>=0;i--) {
        s+=(i+'0');
        v.push_back(stoll(s));
        dfs(s,i);
        s.pop_back();
    }
}

int main() {
    int n;
    cin >> n;
    for(int i=0;i<=9;i++) v.push_back(i);
    
    for(int i=1;i<=9;i++) {
        string s=to_string(i);
        dfs(s,i);
    }
    
    sort(v.begin(),v.end());
    
    if(v.size()<n) cout << -1;
    else cout << v[n-1];
}