[Python] 백준 1038번 - 감소하는 수 (골드 5)

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 브루트포스 알고리즘
 - 백트래킹

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

1038번: 감소하는 수

 

문제

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

입력

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

출력

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

 

---

 

0~무한대의 숫자 중에서 각 자리 숫자가 감소하는 숫자의 N번째를 찾는 문제이다.

 

예를 들어 1은 1번째, 10은 10번째, 20은 11번째, 21은 12번째 와 같다.

 

11은 1과 1로 감소하는 숫자가 아니이기 때문에

10 > 20 > 21 > 30 > 31 > 32 ... 와같다.

 

그러므로 가장 큰 숫자는 9876543210 이 가장 마지막 감소하는 수가 된다.

 

처음엔 단순하게 1~9876543210을 하나하나 문자열로 만들어서 감소하는 것을 확인하였으나

 

당연히 시간초과가 발생했다.

 

---

https://moonsbeen.tistory.com/169

[백준]1038: 감소하는 수 - JAVA

 

위의 블로그를 참고하였다.

 

1로 시작하는 숫자에서 감소하는 수는 1, 10

2로 시작하는 숫자에서 감소하는 수는 2, 20, 21, 210

3으로 시작하는 숫자에서 감소하는 수는 3, 30, 31, 310, 32, 320, 321, 3210

4로 시작하는 숫자에서 감소하는 수는 4, 40, 41, 410, 42, 420, 421, 4210, 43, 430, 431, 4310, 432, 4320, 4321

...

 

위와 같다.

 

이를 전부 뽑아서 정렬한 후 n의 위치의 배열을 찾으면 된다.

 

import sys
input = sys.stdin.readline

n = int(input())

data = []

def find(num, idx):
    if idx > 10: # 숫자는 0~10 은 감소하는 수, 11은 감소하는 수가 아님
        return
    data.append(num)
    for i in range(num%10):
        find(num*10+i, idx+1)
if n <= 10:
    print(n)
else:
    for i in range(10):
        find(i, 1)
        
    data.sort()
    if len(data) <= n: # 찾은 배열의 개수를 넘어서는 n번째는 존재하지 않음
        print(-1)
    else:
        print(data[n])