[백준]1174 줄어드는숫자 #조합

1. 풀이

가장 큰 줄어드는 숫자는 9876543210 이므로 0부터 포문을 돌리면 당연히 시간초과.

재귀적인 방법이나 수학적인 구현으로 문제를 해결하려고 했으나 방법이 떠오르지 않았다.

​

결론은 조합을 이용하여 모든 경우를 다 구하고 N번째를 출력하면 된다.

만들 수 있는 모든 줄어드는 수는 10C1+10C2+10C3...10C10개 이다. (하나의 경우의 수를 뽑은 후 내림차순으로 정렬 시켰을때 특정한 하나의 줄어드는 숫자에 대응 된다.)

즉 경우의 수를 다 합쳐도 1024밖에 되지 않기 때문에 위의 방법으로 풀 수가 있다.

​

*나올 수 있는 경우의 수를 구할 수 있고, 시간복잡도를 계산 후 완전탐색이 가능한, 위와 같은 경우를 유의하자.

​

2. 소스코드

from itertools import combinations
L=[i for i in range(10)]
comb=[]
for digit in range(1,11):
    temp=list(combinations(L,digit))
    for case in temp:
        A=sorted(case)
        num=0
        for i in range(digit):
            num+=(10**i)*A[i]
        comb.append(num)
comb.sort()
N=int(input())
try:
    print(comb[N-1])
except:
    print(-1)