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

📌문제 링크

---

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

📌문제 설명

---

감소하는 수 자체가 많지 않고 최대 큰 값이 9876543210임을 깨닫는것이 중요합니다. 백트래킹으로 가능한 모든 수를 구한 후 정렬을 해줍니다.

📌코드

---

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

public class Main {
    // BufferedReader를 사용하여 입력을 받기 위한 객체
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    // 입력받은 숫자 N
    static int N;
    // 숫자들을 저장할 리스트
    static ArrayList<Long> ls = new ArrayList<>();

    // 입력을 받는 메서드
    public static void input() throws Exception {
        N = Integer.parseInt(br.readLine());
    }

    // 백트래킹을 수행하는 메서드
    public static void backTracking(long num) {
        ls.add(num); // 현재 숫자를 리스트에 추가
        long lastDigit = num % 10; // 마지막 자릿수 계산
        for (long i = 0; i < lastDigit; i++) {
            backTracking(num * 10 + i); // 다음 자릿수를 추가하여 재귀 호출
        }
    }

    // 문제를 해결하는 메서드
    public static void solve() {
        for (long i = 0; i <= 9; i++) {
            backTracking(i); // 0부터 9까지의 숫자로 백트래킹 시작
        }
        Collections.sort(ls); // 리스트를 정렬
        if (ls.size() > N) {
            System.out.println(ls.get(N)); // N번째 숫자 출력
        } else {
            System.out.println(-1); // N번째 숫자가 없으면 -1 출력
        }
    }

    // 메인 메서드
    public static void main(String[] args) throws Exception {
        input(); // 입력 받기
        solve(); // 문제 해결
    }
}