Coding Test
[백준] 감소하는 수
상상쓰
2022. 4. 3. 00:43
https://www.acmicpc.net/problem/1038
1038번: 감소하는 수
음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를
www.acmicpc.net
감소하는 수가 되려면 0 ~ 9 중에서 중복 없이 뽑아 오름차순으로 정렬한 수랑 필요충분조건이 된다.
가장 큰 감소하는 수는 9876543210이며 10C1 + 10C2 + 10C3 + ... + 10C10 = 2^10 - 1 = 1023이며 N = 1022일 때다. (N은 0부터 시작)
즉, N이 1022 보다 크면 -1을 반환하고 그렇지 않으면 combination 과 sort 를 이용하여 N 번째 감소하는 수를 구한다.
import sys
from itertools import combinations
N = int(sys.stdin.readline())
answer = 0
array = []
if N > 1022:
answer = -1
else:
for i in range(10):
for j in combinations(range(10), i+1):
array.append(int(''.join(list(map(str, sorted(list(j), reverse=True))))))
array.sort()
answer = array[N]
print(answer)