1038번 - 감소하는 수

골드 5티어 감소하는 수라는 문제이다.

예를들어 987, 210은 감소하는 수이지만, 100, 200은 감소하는 수가 아니다.

N을 입력받고 N번째 감소하는 수를 구하는 문제이다.

 

문제를 보면 감소하는 수 중 가장 큰 수는 9,876,543,210이다.

크기가 정해져있고, 몇번 써보다보면 감소하는 수는 많지 않다는 느낌이 올 것이다.

즉, list에 감소하는 수를 모두 정리해주고, 그 list에서 해당 감소하는 수를 가져다가 쓰면 된다.

 

list를 만드는 방법은 어떤 수를 맨 앞에 올 수로 정하고, 그 뒤에는 그 수보다 작은 수만 넣어주면 될 것이다.

그리고 한번 정렬 해주고 N번째 요소를 빼주면 된다.

그렇게 나온 식은 다음과 같다.

import java.util.*;

public class Main {
    static int N;
    static ArrayList<Long> list;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        list = new ArrayList<>();
        if (N <= 10) {
            System.out.println(N);
        } else {
            for (int i = 0; i < 10; i++) {
                bp(i,1);
            }
            Collections.sort(list);
            if (N >= list.size()) {
                System.out.println(-1);
            } else {
                System.out.println(list.get(N));
            }
        }
    }
    static void bp(long num, int idx) {
        if (idx > 10) {
            return;
        }
        list.add(num);
        for (int i = 0; i < num % 10; i++) {
            bp((num * 10) + i, idx + 1);
        }
    }
}

bp의 for문을 보면 num % 10이 보이는데, 지금 만들어지고 있는 감소하는 수의 마지막 수를 구하는 것이다.

해당 수보다 작은 수만이 감소하는 수의 맨 마지막 숫자로 올 수 있다.

ex) 21 -> 0 <= 마지막 숫자 < 1
     10 -> 0 <= 마지막 숫자 < 0, 즉 for문이 종료되고 해당 과정은 더이상 실행되지 않음