[JAVA] 백준, 1038번 감소하는 수

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

 

코드

언뜻 보면 쉬운 문제 같으나.... 완전 탐색으로 푸니까 시간 초과가 발생한다.

알고리즘 분류로 브루트포스, 백트래킹이 적혀 있으므로 이를 이용해서 해결해야 한다.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    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 if (n >= 1023) { // 2^10 - 1
            System.out.println(-1);
        } else {
            for (int i = 0; i < 10; i++) {
                traverse(i);
            }
            Collections.sort(list);
            System.out.println(list.get(n));
        }
    }

    static void traverse(long num) {
        list.add(num);
        long val = num % 10;
        if (val == 0) {
            return;
        }
        for (long i = val - 1; i >= 0; i--) {
            traverse((num * 10) + i);
        }
    }
}

---

참고

https://moonsbeen.tistory.com/236