728x90
1038번: 감소하는 수
음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를
www.acmicpc.net
분석
숫자를 덧붙이는 방법으로 한자리, 두자리, 세자리,... 의 감소하는 수 리스트 생성
재귀
n = int(input())
nums = []
def add(idx, num): # 자리수에 따라 증가
if idx == 1:
nums.append(num)
else:
for i in range(num % 10): # 앞자리보다 작은 숫자들만 이어붙이기
add(idx-1, num*10 + i)
for i in range(1, 11):
for j in range(i - 1, 10):
add(i, j)
print(nums[n] if len(nums) > n else -1) # 감소하는 수가 있을 때와 없는 경우
조합
from itertools import combinations
n = int(input())
nums = []
# 반복문을 통해 감소하는 수를 조합
# 최대 감소하는 수는 9876543210
for i in range(1, 11):
for j in combinations(range(10), i):
num = sorted(list(j), reverse=True)
nums.append(int("".join(map(str, num))))
nums.sort() # 감소하는 수 정렬
print(nums[n] if len(nums) > n else -1) # 감소하는 수가 있을 때와 없는 경우
728x90