(Python/🥇5)백준알고리즘 1038번: 감소하는 수

 

문제 바로가기 

감소하는 수

 

문제:

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력:

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

 

출력:

첫째 줄에 N번째 감소하는 수를 출력한다.

 

풀이:

 

 

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


n = int(input())
res = []
result = []

def check(node):
    if len(res) == 1:
        return True
    if res[-2] > node:
        return True
    else: return False

def bt(depth):
    global res
    for i in range(10):
        res.append(i)
        if check(i) == True:
            bt(depth+1)
            result.append(int(''.join(str(x) for x in res)))
        res.pop()
bt(0)
result.sort()
try:
    print(result[n])
except:
    print(-1)

 

1의 자리는 무조건 작아지는 수 이므로 return True 이고

두 자릿수부터, 비교를 해주면 된다.

 

근데 이미 res.append(i) 로 냅다 집어 넣었기 때문에

res[-2] 와 i를 비교해줘야한다.

 

가장 큰 감소하는 수는

9876543210 이다. 1023개가 넘어가면 -1이 리턴된다.