[Baekjoon] 감소하는 수 - Java

문제 

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

 

풀이

n번째로 높은 자리에서 낮은 자리로 감소하는 수를 구하는 문제이다.

 

모든 경우의 수를 따져보면, 총 1023개이다.

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 집합의 부분집합을 구하면 무조건 감소하는 수를 만들 수 있다.

하지만 모두 다 안 고르는 경우

공집합 경우가 있으므로, 총 경우의 수는 1023개이다.

 

1. 10번째 이하일 때는 n을 그대로 출력한다.

 

2. 0 ~ 9사이에서 1자리로 시작해서 10을 나머지 연산한 값보다 작은 값들을 계속 일의 자리로 붙여 리스트에 담는다.

10을 나머지 연산하면 일의 자리가 나오고 그 수보다 작은 값을 붙이면 감소하는 수가 되기 때문이다.

9876543210이 최대 자리이기 때문에, 자릿 수가 10보다 크면 재귀를 빠져나온다.

 

3. 오름차순으로 정렬한다.

 

4. n이 감소하는 수들의 리스트 수 이상이면 -1을 출력하고 그게 아니라면 감소하는 수를 출력한다.

 

소스코드

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

import java.util.ArrayList;
import java.util.Collections;

public class Main {
    private static ArrayList<Long> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        if (n <= 10) {
            System.out.print(n);
            return;
        }

        list = new ArrayList<>();

        for (int i = 0; i < 10; i++) {
            dfs(i, 1);
        }

        Collections.sort(list);

        if (n >= list.size()) {
            System.out.print(-1);
            return;
        }

        System.out.print(list.get(n));

        br.close();
    }

    private static void dfs(long num, int depth) {
        if (depth > 10) {
            return;
        }

        list.add(num);

        for (int i = 0; i < num % 10; i++) {
            dfs((num * 10L) + i, depth + 1);
        }
    }
}

 

실행결과