[BOJ 1174 🥇5] 줄어드는 수 (Python)

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

1174번: 줄어드는 수

문제

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 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

 

⭕ CODE

import sys

input = sys.stdin.readline

n = int(input())

result = []

arr = []

def dfs():
    # arr이 존재하면
    if arr:
        # result에 담아주기
        result.append(int(''.join(map(str,arr))))

    # 0부터 9까지
    for i in range(10):
        # 비어있거나 앞에 수보다 작다면 즉 줄어드는 수라면
        if len(arr) == 0 or arr[-1] > i:
            # 방문표시
            arr.append(i)
            # dfs 실행
            dfs()
            # 초기화
            arr.pop()

# dfs 실행
dfs()

# 정렬해주기
result.sort()

# 에러가 없다면
try:
    # n번째 작은 줄어드는 수 출력
    print(result[n-1])

# 에러가 나오면 불가능한거므로
except:
    # -1 출력
    print(-1)

✏️ Comment

dfs를 사용하여 길이가 1이거나 앞에수보다 작은 수를 만족하면 다시 dfs를 돌렸다.

try except를 사용하여 에러가 나면 불가능한 경우로 -1을 출력