[JAVA] 백준 감소하는 수

처음에는 하나씩 증가하면서 수를 순서대로 잘라서 넣어주는 방식으로 진행했다.

하지만, 그런식으로 진행하게되면 최대값이 몇인지 몰랐고, 효율성 측면에서 순열이 더 좋다고 하여 방식을 바꾸었다.

 

 

각각의 경우에 대하여 일의자리 수에 따른 경우의 수를 구한다

 

일의자리수 각각에 대하여 아래와 같은 방식으로 미리 계산한다.

0: 0

1: 1, 10

2 : 2, 20, 21, 210

3 : 3, 30, 31, 32, 310, 320, 321

...

 

참고로 가장 큰 숫자는 9876543210 이다.

즉, 열자리 숫자이며 이 경우 2^10 -1 = 1024-1 = 1023개이다.

list.size()를 출력해보면 위 결과를 얻을수 있었다.

1023개를 꼭 알아야할 필요는 없다.

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

public class Main {
    static int n;
    static ArrayList<Long> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();

        if (n <= 10) System.out.println(n);//1의자리는 시간단축용용
        else if (n > 1022) System.out.println(-1);
        else {
            for (int num = 0; num < 10; num++) {//1의자리가 0~9까지인 경우들
                cal(num, 1);
            }
            Collections.sort(list);
            System.out.println(list.get(n));
        }

    }

    private static void cal(long num, int depth) {
        if (depth > 10) {//9876543210 : 최대 10자리
            return;
        }
        list.add(num);

        for (int i = 0; i < 10; i++) {
            if (num % 10 > i) {//각각의 경우의수를 다 넣어줌
                cal((num * 10) + i, depth + 1);
            }
        }
        return;
    }

}