boj 1038 감소하는 수

문제 링크

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

문제 풀이

빽트래킹 문제
문제를 0부터 9까지의 수로 시작하는 경우의 수를 생각해보았다.
근데 최대 감소하는 수는 9876543210이므로 최대 자리수는 10자리다.
0부터 9까지로 만들 수 있는 10자리 수는 2 ^ 10 - 1 = 1023개다.
따라서 n이 1023이상이면 -1을 출력해야한다.
빽트래킹은 10의 자리수보다 작은 수를 재귀를 통해 감소하는 수를 만든다.

전체 코드

package BOJ;

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

public class 감소하는수 {

    static List<Long> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        if (n <= 10) {
            System.out.println(n);
        } else {
            for (int i = 0; i < 10; i++) {
                dfs(i, 0);
            }
            if (list.size()-1 < n) {
                System.out.println(-1);
                return;
            }
            Collections.sort(list);

            System.out.println(list.get(n));

        }
    }

    private static void dfs(long num, int idx) {
        if (idx > 10) {
            return;
        }

        list.add(num);
        for (int i = 0; i < num % 10; i++) {
            long newNum = (num * 10) + i;
            dfs(newNum, idx + 1);
        }
    }
}