[C++][백준][정렬] 1174 줄어드는 숫자

https://www.acmicpc.net/problem/1174

1174번: 줄어드는 숫자

문제

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

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

입력

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

출력

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

예제 입력 1

1

예제 출력 1

0

 

 

1~9의 숫자라면 N-1을 출력하고 

줄어드는 수 중 가장 큰 수인 9876543210 는 2^10-1번째니까 N이 1023을 넘어가면 -1을 출력한다.

decrease함수는 순환을 이용해서 N번째 작은 줄어드는 수를 구해 출력한다.

 

 

#include <stdlib.h>
#include <stdio.h>
 
int num[1000];
int N,t;
 
void decrease(int a, int c, int s) {
    if (a==c){
        t++;
        if (t==N){
            for (int i=0; i<a; i++)
                printf("%d",num[i]);
            printf("\n");
        }
    }
    else if (a>c)
        return;
    else {
        for (int i=0; i<= s; i++) {
            if (i==0 && a+1 != c)
                continue;
            num[a] = i;
            decrease(a+1, c, i-1);
        }
    }
}
 
int main(){
    scanf("%d", &N);
 
    if(N<=10)
        printf("%d\n",N-1);
    if(N>1023)
        printf("-1\n");
    else {
        t=10;
        for (int i=2; i<1000; i++) {
            decrease(0, i, 9);
        }
    }
}