문제 1038번

소스코드

import java.io.*;
import java.util.*;
public class boj1038 {
    static List<Long> list;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        /*
            최대가 되는 감소하는 수 : 9876543210
            해당 수는 1022번째 값이다.
         */
        if(n >1022){
            System.out.println(-1);
        }else {
            list = new ArrayList<>();
            for (int i = 0; i < 10; i++) {
                solution(i, 1);
            }
            Collections.sort(list);
            System.out.println(list.get(n));
        }
    }
    public static void solution(long num, int len){
        if(len >10){
            return;
        }
        list.add(num);
        for (int i = 0; i < 10; ++i) {
            if(num%10 >i){
                solution((num*10)+i, len+1);
            }
        }
    }
}

풀이 접근

1. 감소하는 수의 최대 숫자는 9876543210이다.
2. 감소하는 수를 담을 list를 만든다.
3. 맨 앞에 들어갈 숫자를 기준으로 감소하는 수를 담을 재귀함수를 구현한다.
   만약 길이가 10이 넘는 수가 나온다면 감소하는 수가 존재하지 않으니 재귀를 끝낸다.

public static void solution(long num, int len){
    if(len >10){
        return;
    }
    list.add(num);
    for (int i = 0; i < 10; ++i) {
        if(num%10 >i){
            solution((num*10)+i, len+1);         
        }
    }
}

4. 감소하는 수가 들어있는 리스트를 오름차순으로 정렬한다.
5. list의 사이즈를 보면, 9876543210은 1022번째에 있다는 것을 알 수 있다.
6. 예외처리로 n이 1022 초과로 들어오면 -1을, 아니라면 list.get(n)으로 값을 출력한다.

문제 핵심

• 백 트래킹