[BOJ]1174 - 줄어드는 수 (G5)

문제 링크

1174-줄어드는 수

입력

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

출력

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

문제 풀이

숫자를 만들기 위해서는 10개의 숫자를 선택하냐 선택하지 않냐의 문제이기 때문에
총 2^10개의 경우의 수가 나온다.
이 수를 넘어가는 n을 입력ㅂ다는다면 n번째로 작은 줄어드는 수가 존재할 수 없다.

내림차순으로 정렬된 배열과 재귀함수를 만든다.
재귀함수 내부에서는 내가 만들어 둔 배열의 현재 수를 선택하냐, 하지 않느냐
두 가지 경우만 존재하기 때문에 각각의 경우 재귀함수를 호출한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<Long> arr = new ArrayList<>();
    static int[] nums = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        makeList(0, 0);
        Collections.sort(arr);

        if(n>1023) System.out.println(-1);
        else System.out.println(arr.get(n - 1));
    }

    static void makeList(long num, int idx) {
        if(!arr.contains(num)) arr.add(num);
        if (idx >= 10) return;

		// 현재의 수를 선택하느냐 선택하지 않느냐가 가능한 경우의 수
        makeList(num * 10 + nums[idx], idx + 1);
        makeList(num, idx + 1);
    }

}