백준-1038-감소하는 수(파이썬)

문제이해

• N이 주어지면 N번째 감소하는 수를 구하는 문제이다
• 예를 들어 921은 감소하는 수이다.

문제생각

• 일단 가장 큰 감소하는 수를 9876543210 이다.

• 1자리 수의 경우 > 1~9까지 9개

• 2자리 수의 경우

  • 10 / 20, 21 / 30, 31, 32 / 40, 41, 42, 43 / ~ / 90, 91...98 = 55개

• 3자리 수의 경우

  • 210 / 310, 320, 321 / 410, 420, 421, 430, 431, 432 / ...

• 위에서 수를 나열하면서 보니 하나의 규칙이 보이는 것 같다.

• 생각해보니 조합을 사용하면 될 거 같다.

• 각 자리 수 별로 모든 조합을 하고 그 값들을 저장한 뒤 N번째 수를 출력하면 되는 것이다.

  문제풀이

  import sys
  from itertools import combinations
  input=sys.stdin.readline
  
  n=int(input())
  
  nums=[]
  for i in range(1, 11):
     comb_list=combinations(range(0, 10), i)
     for comb in comb_list:
         comb=list(comb)
         comb.sort(reverse=True)
         nums.append(int(''.join(map(str, comb))))
  
   nums.sort()
   try:
       print(nums[n])
   except:
       print(-1)