[BOJ/백준] 1038 감소하는 수

# 1038 감소하는 수
# X의 자릿수가 가장 큰 자릿수
import collections
def dfs(N):
    deque = collections.deque()
    for i in range(1,10):
        deque.append((i,str(i)))
    while deque:
        if len(result) == N+1:
            break
        cur_num,to_num = deque.popleft()
        if cur_num != 0:
            for k in range(cur_num):
                temp = to_num + str(k)
                deque.append((k,temp))
                result.append((temp))


N = 1023
result = []
for i in range(10):
    result.append(i)

if N >=10:
    dfs(N)
if len(result) > N:
    print(result[N])
else:
    print(-1)

 기본적인 백트래킹 문제이다. 처음에 1~9의 수를 넣어주고, 그보다 낮은 자리수에서 더 낮은 값을 넣어주면서 결과값에 넣어주고, 해당 길이를 초과하는 N이 나올시에는, -1을  출력하도록 했따.