[백준 1038] 감소하는 수(Java)

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

이 문제는 재귀함수를 이용하여 구현할 수 있습니다.

이 문제의 핵심은 감소하는 수를 어떤 식으로 생성하느냐입니다. 이는 감소하는 수의 특성을 이해하면 쉽게 구현할 수 있습니다. 감소하는 수는 이전 자릿수의 수보다 작은 수입니다. 따라서 현재 자릿수의 수보다 작은 수를 그 뒤에 계속 추가하는 방식으로 구현이 가능하며, 재귀함수의 성질을 이용하여 자릿수와 값 정보를 받아 자신의 뒤에 값보다 작은 수를 리스트에 추가하는 방식으로 구현이 가능합니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main{
    static List<Long> arr = new ArrayList<>();

    public static void main(String[] args) throws Exception{
        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++) set(i,1);
            if(N >= arr.size()) System.out.println(-1);
            else{
                Collections.sort(arr);
                System.out.println(arr.get(N));
            }
        }
    }

    static void set(long num, int val){
        if(val > 10) return;

        arr.add(num);
        for(int i=0;i<num%10;i++){
            set((num*10)+i, val+1);
        }
    }
}