[Baekjoon] 1174번 : 줄어드는 수

1. 문제

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

• 백트래킹, DFS 문제

// 문제
음이 아닌 정수를 십진법으로 표기했을 때, 
왼쪽에서부터 자리수가 감소할 때, 
그 수를 줄어드는 수라고 한다. 
예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 
만약 그러한 수가 없을 때는 -1을 출력한다. 
가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.

// 입력
N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

// 출력
첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

// 예제 입력 1 
1

// 예제 출력 1 
0

// 예제 입력 2 
19

// 예제 출력 2 
42

// 예제 입력 3 
500000

// 예제 출력 3 
-1

2. 핵심 아이디어

-

3. Python 문제풀이

import sys
input = sys.stdin.readline

arr = list()
result = set()

def dfs() :
  if len(arr) > 0 :
    result.add(int("".join(map(str, arr))))

  for i in range(0, 10) :
    if len(arr) == 0 or arr[-1] > i :
      arr.append(i)
      dfs()
      arr.pop()

n = int(input())

try :
  dfs()
  result = list(result)
  result.sort()
  print(result[n-1])
except :
  print(-1)

4. Java 문제풀이