BOJ 1174 - 줄어드는 수

문제

왼쪽에서 오른쪽으로 갈수록 각 자릿수가 감소하는 수를 줄어드는 수라 한다. N번째로 작은 줄어드는 수를 구하라.

입력

첫째 줄에 N이 주어진다.

출력

N번째 줄어드는 수를 출력한다. 없으면 -1을 출력한다.

예제

입력	출력
`1`	`0`

풀이

9~0 중 부분집합을 선택하여 내림차순으로 나열하면 줄어드는 수가 된다. DFS로 모든 경우를 생성한다.

숫자 배열 {9, 8, 7, ..., 0}에서 DFS로 각 원소를 선택하거나 건너뛰며 수를 생성한다
선택한 숫자를 기존 수 뒤에 이어붙이면 자동으로 감소 순서가 유지된다
생성된 모든 수를 리스트에 저장하고 정렬한다
N번째 수를 출력하며, 범위를 초과하면 -1을 출력한다

핵심 아이디어: 줄어드는 수는 {9,8,...,0}의 부분집합과 1:1 대응되므로 최대 2^10 = 1,024개만 존재한다.

코드

package day799;
 
import java.io.*;
import java.util.*;
 
public class Day779BOJ1174줄어드는수 {
 
  static int n;
  static int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
  static List<Long> list = new ArrayList<>();
 
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    n = Integer.parseInt(br.readLine());
 
    dfs(0, 0);
    list.sort(null);
 
    try {
      System.out.println(list.get(n - 1));
    } catch (Exception e) {
      System.out.println(-1);
    }
 
  }
 
  private static void dfs(long num, int index) {
    if (!list.contains(num)) {
      list.add(num);
    }
 
    if (index >= 10) {
      return;
    }
 
    dfs((num * 10) + arr[index], index + 1);
    dfs(num, index + 1);
 
  }
}

복잡도

시간: O(2^10)
공간: O(2^10)

문제