✍ 문제

문제링크: https://www.acmicpc.net/problem/1038

👏 풀이과정

백트래킹으로 푸는 문제이다. 이 문제를 풀 때 고민해야 되는 부분이 있는데 int의 최대값을 생각해 줘야 한다.
int형으로 하면 987654321이 감소하는 수 중에 제일 큰 값이지만 Long형으로 해주면 9876543210이 제일 큰 감소하는 수 이기 때문에 이 부분을 잘 고려해줘야 한다.

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    static LinkedList<String> queue = new LinkedList<>();
    static int N =1021;
    static int count = -1;
    static String present ;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for(int i = 0; i < array.length; i++){
            queue.add(Integer.toString(array[i]));
            count++;
            if(N == count){
                System.out.println(array[i]);
                return;
            }


        }
        while(!queue.isEmpty()){
            present = queue.poll();

            for(int i = 0; i < 10; i++){
                if(Integer.parseInt(present.substring(present.length() - 1,present.length())) > i ){

                    queue.add(present + Integer.toString(i));
                    count++;
                    if(count == N){
                        System.out.println(Integer.parseInt(present + Integer.toString(i)));
                        return;
                    }
                    if(N == 1022){
                        System.out.println(9876543210L);
                        return;
                    }
                    if(N > 1022){
                        System.out.println(-1);
                        return;
                    }
                }

            }

        }
    }


}