[Python] 백준 1038 감소하는 수

1. 문제 링크

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

1038번: 감소하는 수

 

2. 문제 요약

n번째 감소하는 수를 찾는 문제이다. 9876543210 이후로 감소하는 수는 없기 때문에 그 이후 수는 -1을 출력한다.

---

3. 아이디어 정리

1. 0~9로 1개~10개까지 모든 조합을 구한다. 
2. 오름차순을 하여 정렬을 진행한다.
3. 해당 수를 출력하거나 인덱스 에러가 나면 해당 순서 감소하는 수가 없는 것이라 -1 출력한다.

---

4. 문제 풀이

4-1. 내 풀이

import sys
from itertools import combinations

n = int(sys.stdin.readline())

nums = list()               # 모든 감소하는 수
for i in range(1, 11):      #  1~10개의 조합 만들기 (0~9개니깐)
    for comb in combinations(range(0, 10), i):  # 0~9로 하나씩 조합 만들기
        comb = list(comb)
        comb.sort(reverse=True)                     # 해당 조합을 감소하는 수로 변경
        nums.append(int("".join(map(str, comb))))

nums.sort()   # 오름차순

try:
    print(nums[n])
except:     # 인덱스가 넘어가는 경우 -1 출력. 마지막 수 9876543210
    print(-1)

 

---

5. 결론

• 조합을 이용한 문제