[백준] 1174 - 줄어드는 수 / Python / 골드 5

🚩문제 주소

📄풀이

백트래킹

줄어드는 수는 최대 9876543210까지 있으므로 0부터 9까지 백트래킹을 활용하여 줄어드는 수들을 만들어 줍니다.

set을 활용해 중복되는 수들을 제거해주고 sort로 작은 순서대로 정렬시킵니다.

N-1번 째 수를 출력합니다.

👨‍💻코드

def dfs():
  if len(arr) > 0:
    answer.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())
arr = []
answer = set()
dfs()
answer = list(answer)
answer.sort()

try:
  print(answer[N-1])
except:
  print(-1)