[ BOJ ][JAVA][1038] 감소하는 수

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

1038번: 감소하는 수

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	15287	4089	3227	30.193%

문제

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

입력

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

출력

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

예제 입력 1

18

예제 출력 1

42

접근

1 : 1 10
2 : 20 21 210 ...
3 : 30 32 31 310 320 321 ...
4 : ...

집합 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 에서 공집합이 아닌 임의의 부분집합 ex) {1, 3, 5, 9}일 때
이 집합에 대응되는 감소하는 수는 무조건 1개로 고정이다.

수를 감소하게 둬야하기 때문.
따라서, 감소하는 수는 2^10 - 1 = 1023개밖에 없다.

코드

/*
    감소하는수 (Gold 5)
*/
import java.io.*;
import java.util.*;

public class p1038 {
    static int n;
    static List<Long> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        if (n <= 10) {
            System.out.println(n);
        } else if (n > 1022) {
            System.out.println("-1");
        } else {
            for (int i = 0; i < 10; i++) {
                solution(i, 1);
            }
            Collections.sort(list);
            System.out.println(list.get(n));
        }
    }

    // ex) n: 4
    // list.add(0), list.add(1), list.add(2), list.add(3), .... , list.add(9)
    // list.add(10)
    // list.add(20), list.add(21)
    // list.add(30), list.add(31), list.add(32)
    // ...

    static void solution(long num, int idx) {
        if (idx > 10) {
            return;
        }
        list.add(num);
        for (int i = 0; i < num % 10; i++) {
            solution((num * 10) + i, idx + 1);
        }
    }
}