[BOJ/Python] 1038번 문제풀이

문제 설명

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

입력

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

출력

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

---

풀이 과정

우선 문제가 잘 이해 안되서 검색해서 찾아보았고, 그 결과 감소하는 수의 특징은 아래와 같았다.

1. 한 자리 숫자는 그 자체만으로도 감소하는 수이다.

사실 문제 설명만으로 잘 이해 못했던 부분이었는데, 설명 그대로 생각하면 되는 것이었다.

설명에 나와있는 것처럼 0은 0번째, 1은 1번째 감소하는 수이다. 즉, 0~9는 그 숫자만으로도 0~9번째 감소하는 숫자라는 것이다.

 

2. 두 자리 이상의 숫자들

두 자리 이상부터 감소하는 수를 구하는 방법은 다음과 같다.

감소하는 숫자는 '내림차순'을 유지한 채로 숫자가 이루어져 있는 수를 말한다. 즉, 10이라는 감소하는 숫자는 감소하는 숫자 21보다 더 먼저 나오는 숫자이다. 따라서 21이 10 보다 먼저 등장하는 감소하는 수라고 판단해서는 안된다.

 

두 자리 이상의 감소하는 수를 구하는 방법은 다음과 같다. 바로 '가장 마지막 숫자보다 더 작은 숫자들은 추가적으로 붙이면 되는 것'이다. 현재까지 감소하는 수는 [ 0 1 2 3 4 5 6 7 8 9 ] 이므로 그 다음 감소하는 수를 구해보자.

0보다 더 작은 숫자는 존재하지 않으므로 0뒤에 더 작은 추가적인 숫자들을 붙일 수 없다.

1은 1보다 더 작은 숫자인 0을 붙이니 10이 되었다. 즉, 10번째 감소하는 숫자는 10이 된 것이다. 그 다음 2뒤에 작은 숫자들인 0과 1을 붙이니 20, 21이 나왔다 이런식으로 N번째 숫자까지 반복을 하면 된다.

 

이러한 내용을 바탕으로 파이썬으로 코드를 작성해보았다.

사실 어떻게 코드를 짜야할지 감이 안와서 구글링으로 문제 이해해가면서 풀었다...

import sys
from itertools import combinations

a = int(sys.stdin.readline())
answer = []

# 반복문을 통해 감소하는 수를 조합
# 최대 감소하는 수는 9876543210
for i in range(1, 11):
    for j in combinations(range(10), i):
        num = sorted(list(j), reverse=True)
        answer.append(int("".join(map(str, num))))

answer.sort() # 감소하는 수 정렬
print(answer[a] if len(answer) > a else -1)  # 감소하는 수가 있을 때와 없는 경우

 

[참고자료]

https://fre2-dom.tistory.com/487

https://yabmoons.tistory.com/553