백준 알고리즘 1038번 감소하는 수 풀이 With Python

문제 링크: www.acmicpc.net/problem/1038

1038번: 감소하는 수

문제는 N번째 감소하는 수를 구하는 것입니다. 처음에 이 문제를 보면 상당히 막막하지만, 천천히 생각해보면 의외로 간단합니다. 저는 1 자릿수부터 10 자릿수까지(9876543210) 천천히 숫자를 만들고 이때마다 count 수를 늘려서 count수가 N과 같아질 때 감소하는 수를 출력하도록 하였습니다. 파이썬으로 해결한 코드는 아래와 같습니다.

import sys

n = int(sys.stdin.readline())
# 0번째 수는 0이므로 count는 -1부터 시작합니다.
count = -1
# answer값을 -1로 선언합니다.
answer = -1


def solution(limit, sub):
    global count
    global answer
    if len(sub) == limit:
        count += 1
        # count가 n과 같아지는 순간 숫자를 출력하고 종료합니다.
        if count == n:
            answer = int(sub)
            print(answer)
            sys.exit()
        return
    else:
    	# 가장 처음일 경우 맨앞자리 숫자를 limit-1부터 9까지로 만듭니다.
        if sub == '':
            for i in range(limit - 1, 10):
                sub += str(i)
                solution(limit, sub)
                sub = ''
        else:
            for i in range(int(sub[-1])):
                if limit - len(sub) - 1 > i:
                    continue
                sub += str(i)
                solution(limit, sub)
                sub = sub[:-1]


for k in range(1, 11):
    solution(k, '')
print(-1)

 소스코드에 대해 질문이 있으시면 댓글 남겨주시면 답변드리겠습니다.