[Python] 백준 1038번 : 감소하는 수

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

1038번: 감소하는 수

---

💡 문제 풀이

백트래킹인줄 알고 풀었는데 브루트 포스로 풀었다.

 

조합을 이용해서 각 자릿수 별로 만들 수 있는 모든 값들을 만든다. 

정렬을 통해서 감소하는 수를 만들어주고 배열에 넣어준다.

감소하는 수를 담은 배열을 정렬해주면 순서대로 감소하는 수를 찾을 수 있다.

✔️ 느낀 점

보자마자 가장 큰 값은 9876543210 이라고 생각했다. 범위가 생각보다 크지 않아서 모두 담아버린 다음에 그 중에서 찾으면 될 것이라고 생각했다. 되게 야무진 문제라고 생각한다.

💻 코드

from itertools import combinations

n = int(input())

numbers = []
for i in range(1, 11):
    for c in combinations(range(0, 10), i):
        c = list(c)
        c.sort(reverse=True)
        numbers.append(int("".join(map(str, c))))

numbers.sort()

try:
    print(numbers[n])
except:
    print(-1)