[Java] [백준 1038][Brute-force] 감소하는 수

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

---

문제 풀이

이 문제는 처음에 풀때 DP를 이용해서 풀다가 너무 복잡해져서 규칙을 적용하기가 힘들었다.

 

그런데 브루트 포스로 풀게 되면 순서와 상관없이 계속 넣을 수 있고 애초에 9876543210이 구할 수 있는 최대값이기 때문에 N이 1000000까지 계산할 필요가 없다.

 

순서와 상관없이 넣은 다음에 나중에 sort하는 방식을 선택하였다.

 

먼저 1 뒤에는 0만 올 수 있으니 1과 10 - 2가지

2 뒤에는 1과 0이 올 수 있으니 2 20 21  - 3가지

3 뒤에는 2, 1, 0 이 올 수 있으니 3, 30, 31, 32, 310, 320, 321 - 7가지

....

 

이런식으로 규칙을 정해서 계속 리스트에 저장시켜 주고 솔트하면 된다.

 

10 이하일 경우에는 그냥 N을 출력하면 되니까 시간 단축을 위해 조건문을 사용했다.

 

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

public class Main {
	static ArrayList<Integer> list;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		list = new ArrayList<>();

		// 9876543210 -> max

		if (N <= 10) {
			System.out.println(N);
		} else if (N > 1022) {
			System.out.println(-1);
		} else {
			for (int i = 0; i < 10; i++) {
				Cal(i, 1);
			}
			// 순서대로 저장이 안되어있기 때문에 sort가 필요함.
			Collections.sort(list);
			System.out.println(list.get(N));
		}

	}
	
	private static void Cal(int num, int depth) {
		//9876543210 이 마지막임. 총 10자리.
		if (depth > 10) {
			return;
		}
		list.add(num);
		
		// 처음에 num이 0이면 pass 
		// num이 1이면 i가 0일때만. => 1뒤에 올수있는 감소하는 수들... 1 , 10
		// num이 2면 2,20, 21, 210 
		// num이 3이면 3, 30, 31,310,32,320,321,322
		// ..이런식으로 9까지
		for (int i = 0; i < 10; i++) {
			if (num % 10 > i) {
				Cal((num * 10) + i, depth + 1);
			}
		}
		return;
	}

}