BOJ 1174

줄어드는 수 성공

 

2 초

128 MB

3158

1230

1012

41.188%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

1

예제 출력 1 복사

0

예제 입력 2 복사

19

예제 출력 2 복사

42

예제 입력 3 복사

500000

예제 출력 3 복사

-1​

0~9개의 카드가 있다고 했을때, 이 카드를 순서에 상관없이 특정한 개수만큼 뽑는, 조합의 문제이다.

모든 노드(0~9)는 1 아니면 0이 될 수 있으니 경우의수는 1024개 이지만, 0개를 뽑는 경우의수는 이 문제에선 존재하지 않기 때문에 -1개를 해주어 총 1023개이다.

 

개수가 적으므로 모든 조합에 해당하는 숫자를 전부 구해, 정렬해주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int N, arr[10];
vector<long long>v;
void func(int n, int l, int k){
    if(n == k){
        long long ans=0;
        int p = 0;
        for(int idx=0; idx<10; idx++){
            if(arr[idx]){
                ans += idx * pow(10, p);
                p += 1;
            }
        }
        v.push_back(ans);
        return;
    }
    for(int i=l; i<10; i++){
        if(arr[i]) continue;
        arr[i] = 1;
        func(n+1, i, k);
        arr[i] = 0;
    }
}
int main(){
    cin>>N;
    if(N > 1023){
        cout<<-1;
        return 0;
    }
    for(int i=1; i<=10; i++)
        func(0,0,i);
    sort(v.begin(), v.end());
    cout<<v[N-1];
}