[백준] 1038 감소하는 수 - python 파이썬

문제

 

 

처음 이 문제를 접했을 때는 감이 전혀 안잡혔다.. 범위가 너무 커서 하나하나 구하는 방식으로는 무조건 시간초과가 날 것 같은데 딱히 다른 방법이 생각나질 않았다

 

그래서 구글링의 도움을 받은 결과 "조합" 을 사용해서 풀 수 있다는 것을 알게 되었다.

 

 

조합이면 더 시간 초과 나는거 아냐?? 할 수도 있지만 사실 최대 감소하는 수는 정해져있다 9876543210 으로 10자리 숫자이다.

그러므로 10자리 숫자까지의 조합을 구해주면 되는데

 

여기서 중요한건

 

감소하는 수  = 서로 다른 숫자의 모임

 

이라는 것이다. 동일한 숫자가 있는 경우는 감소하는 수가 아니기때문에 감소하는 수는 각 자리의 숫자가 모두 다르다.

그리고 각 자리의 숫자가 내림차순으로 정렬된 것으로 보면 된다.

 

 

결론은

 

1자리 숫자부터 10자리 숫자까지 구하는 것 =  숫자 1개의 조합 ~ 숫자 10개의 조합

 

이 되며 이 숫자의 조합이 내림차순 정렬 된 것이라고 생각해주면 된다.

 

 

 

정답 코드

from itertools import combinations
n = int(input())

ans = []
#i자리수 숫자 조합 구하기
for i in range(1,11):
    #0부터 9까지 숫자 중 i개의 조합
    for j in combinations(range(10),i):
        #감소하는 수 이므로 내림차순 정렬
        num = sorted(list(j), reverse= True)
        ans.append(int("".join(map(str,num))))
ans.sort()
print(ans[n] if len(ans)>n else -1)