[BOJ] 줄어드는 수 1174번 C++

 

 

문제

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.

입력

N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

 

접근 방식

 

먼저 줄어드는 수를 만들수 있는 모든 가짓수를 만든다

이때 만들수 있는 최대 줄어드는 수는 987,654,321이기 때문에 2초안에 가능하다

 

만든 수를 모두 정렬하고 만약 만든 모든 수의 개수가 N보다 작다면 N-1인덱스의 값을 출력하고 크다면 -1을 출력하면 된다!

 

처음에는 잘 이해가 가지 않았는데 두번 세번 다시 생각해보니 조금 이해가 되었다..!

 

 

코드

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

typedef long long ll;

vector<ll> v;

void sol(ll num, int last) {

    for(int i=0; i<last; i++) {
        ll new_num = num * 10 + i;
        v.push_back(new_num);
        sol(new_num, i);
    }


}

int main() {
    int N; cin>>N;

    for(int i=0; i<10; i++) {
        v.push_back(i);
        sol(i, i);
    }

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

    if(N <= v.size()) cout<<v[N-1];
    else cout<<-1;
}