백준_브루트포스_감소하는 수_1038_파이썬

✅문제

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

✅입력

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

✅출력

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

ㅤ

✅알고리즘 분류

• 브루트포스
• 백트래킹
  ㅤ

💡풀이

1. 감소하는 수의 최대 값은 9876543210이다.
2. 현재 숫자의 뒤에 1부터 현재 숫자부터 작은 숫자를 하나씩 더한다.
3. 더한 숫자의 길이가 현재 M값의 길이와 같다면 찾은 감소하는수 +1
4. 감소하는수의 순서가 N과 같다면 출력

N = int(input())
if N < 10:
    print(N)
    exit()
num = 10
cnt = 9


def assemble(n, word):
    global cnt

    if n == M:      # 해당 숫자의 길이가 다 되면 감소하는 수인지 검사
        cnt += 1
        if cnt == N:
            print(word)
            exit()
        return

    for i in range(int(word[-1])):
        new = word + str(i)
        assemble(n+1, new)


while num <= 10000000000:
    M = len(str(num))       # 숫자의 길이
    top = str(num)[0]       # 가장 큰 수

    assemble(1, str(top))
    num += 10**(M-1)
else:
    print(-1)

ㅤ

📌 배운 점

• 문제가 찾는 답의 최댓값을 먼저 짚고 가는 것이 중요했던 문제다. 그 부분을 인지하지 못하고 진행하니까 오류가 잦았다.
• 숫자와 문자를 인덱스순회하며 찾을 수 있고, 예외 범위를 걸러내는 능력(백트래킹)을 기르기 좋은 문제다