[백준 1038번] 감소하는 수

문제 설명

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

접근 방식 및 풀이

n번째 감소하는 수를 구하는 문제이기 때문에 0번째부터 n번째까지 올라가면서 찾아야겠다고 생각했다. 만약 모든 숫자를 확인하면서 올라가게 되면 시간이 너무 오래 걸릴 것이다. 하지만 모든 숫자를 확인할 필요가 없다. 어떻게 하면 될까?

우선, 자리수 별로 감소하는 수를 나누어보겠다. 0번째부터 9번째 감소하는 수는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9가 된다. 여기까지가 한자리다. 두자리에선 10, 20, 21, 30, 31, 32, … 순서로, 세자리에선 210, 310, 320, 321, … 순서로 올라간다. 우리가 현재 세자리의 감소하는 수를 구할 차례라고 가정해보자. 100부터 999까지 모든 숫자를 확인해야만 할까? 아니다. 두자리의 감소하는 수를 활용하면 시간을 대폭 줄일 수 있다.

세자리의 감소하는 수들의 맨 앞의 수를 없애보자 그럼 10, 10, 20, 21, …이 된다. 어디서 많이 본 숫자 같아보인다. 바로 두자리의 감소하는 수들이다. 감소하는 수란 가장 큰 자릿수부터 작은 자릿수까지 감소하는 수를 의미하기 때문에 앞에 숫자를 하나 없애도 계속 감소하는 수라는 것을 알 수 있다.

결국 맨 앞자리 숫자를 정하고 해당 숫자보다 작은 숫자로 시작하는 x자리의 감소하는 수를 뒤에 넣으면 x+1자리 감소하는 수를 구할 수 있는 것이다. 맨 앞자리 숫자는 0부터 시작해서 9까지 넣고 끝나면 다음 자리의 수로 넘어간다.

이런 과정을 반복하다가 n번째 감소하는 수가 나오면 해당 수를 출력하고 종료한다. 마지막 감소하는 수인 9876543210까지 나왔는데도 n번째 감소하는 수가 나오지 않았다면, n번째 감소하는 수는 존재하지 않으므로 -1을 출력한다.

코드

문제 풀이에 사용한 언어: C

#include <stdio.h>
#include <math.h>

int main(){
    int n;
    scanf("%d", &n);
    
    long long num[10000]; // 감소하는 수를 저장하는 배열
    int first, last; // 한자리 아래의 감소하는 수의 범위를 나타낸다.
    int cur; // 다음 나오는 감소하는 수를 넣을 위치
    
    for(int i = 0; i < 10; i++) // 0~9번째까지는 그대로 0~9를 넣는다.
        num[i] = i;
    
    first = 0; // 한자리 숫자들은 0부터
    last = 9; // 9까지 들어가 있다.
    cur = 10; // 0~9까지 넣었으므로 다음 위치는 10
    
    for(int i = 1; i < 10; i++){ // 10의 몇승인지를 나타낸다. ex) i가 2이면, 10의 2승인 백 대 수들 = 세자리 수들
        for(int j = i; j < 10; j++){ // j는 현재 수의 맨 앞자리 숫자를 의미한다. ex) j가 3이면, 3xx
            for(int k = first; k <= last; k++){ // 한자리 아래의 감소하는 수들을 확인해서 ex) 두자리 수 중 감소하는 수 = 10, 20, 21, 30, 31 등
                if(num[k] / pow(10.0, i-1) < j){ // 해당 수의 맨 앞자리 숫자가 j보다 작다면 ex) 위의 숫자 중 10, 20, 21만 해당한다.
                    num[cur++] = j * pow(10.0, i) + num[k]; // 해당 감소하는 수의 맨 앞에 j를 추가했을 때 감소하는 수가 된다. 그러므로 감소하는 수 배열에 추가 ex) 310, 320, 321 추가
                    if(cur > n){ // n번째 감소하는 수를 찾았다면
                        printf("%lld\n", num[n]); // n번째 감소하는 수 출력
                        return 0;
                    }
                }
            }
        }
        first = last + 1; // 한자리 위의 감소하는 수 중에 첫번째를 가르킴
        last = cur - 1; // 한자리 위의 감소하는 수 중에 마지막을 가르킴
    }
    
    printf("-1\n"); // n번째 감소하는 수가 없으므로 -1 출력
    return 0;
}