[백준] 1038 감소하는 수

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

 

풀이

찾고자 하는 값은 N 번째 감소하는 수를 찾아내면 된다.

 

N번째 감소하는 수를 찾는 법은 굉장히 간단하다. 1~9까지 각 숫자로 시작하는 경우에서 나올 수 있는 값들을 찾으면 된다.

 

예시를 들어보면

 

가장 큰 자릿수가 2라고 했을 때 

 

2, 20, 21, 210 이런 값들을 구해 나가면 된다. 

 

해당 값들은 재귀를 통해서 찾아낼 수 있다. 

 

% 10을 하는 이유는 해당 값의 1의 자리 수 다음으로 올 수 있는 값의 범위를 알아야 하기 때문이다. 

예시로 num = 543일 경우 1의 자리 3 다음으로 올 수 있는 경우는 0,1,2

재귀(int num) {
	for(int i = 0; i < num % 10; i++) {
    	재귀(num *10 + i);
    }
}

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static List<Long> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        for (long i = 0; i < 10; i++) {
            rec(i);
        }
        //N이 감소하는 수 전체 개수보다 클 경우
        if (n >= list.size()) {
            System.out.println(-1);
            return;
        }
        //감소하는 수 정렬
        Collections.sort(list);
        System.out.println(list.get(n));
    }

    private static void rec(long num) {
        list.add(num);
        for (int i = 0; i < num % 10; i++) {
            rec(num * 10 + i);
        }
    }
}