Baekjoon 1038. 감소하는 수 / Python

1038. 감소하는 수

난이도 : 골드 5
소요 시간 : 20분
날짜 : 2025.01.02
언어 : 파이썬
알고리즘 유형 : 완전탐색, 백트래

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다.
2. n번째 감소하는 수를 출력하라 없다면 -1을 출력하라.

2. 해결 방식

1. 감소하는 수를 다 구해놓고, 출력한다.
2. 감소하는 수 구하기
   • 9876543210 에서 완전탐색으로 하나씩 빼면서 집합에 집어넣는다.
   • 그 후 정렬한다.

3. 정답 코드

import sys
# input = sys.stdin.readline
sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")
sys.setrecursionlimit(10**5)

res = set()
def dfs(n:int, x:str='9876543210'):    # n: 원하는 자리 수, x:현재 str값
    global res
    if len(x) == n:
        res.add(int(x))
        return

    dfs(n, x[1:])
    dfs(n, x[:-1])
    if len(x) > 2:
        for i in range(1, len(x) - 1):
            dfs(n, x[:i] + x[i+1:])

for i in range(1, 11):
    dfs(i)

try:
    print(sorted(res)[int(input())])
except IndexError:
    print(-1)