백준 1038. 감소하는 수 (Python)

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

풀이

참고로 이문제는 1174번(줄어드는 수)와 99% 유사하다.
백트래킹 혹은 조합을 통해 0부터 1000000까지의 줄어드는 수 조합을 찾는다.

이때,최대 감소하는 수(9876543210)는 N이 1022번째일때의 경우이므로, 그 이상으로 N이 들어올 경우 -1출력 처리.

N=int(input())
li=[]

def func(x,idx):
    global li
    if x!='':
        li.append(int(x))

    for i in range(idx+1,10):
        func(str(i)+str(x),i)

if N>1022:
    print(-1)
else:
    func('',-1)
    li.sort()
    print(li[N])
print(li)

from itertools import combinations
N=int(input())
li=[]
if N>1022:
    print(-1)
else:
    for i in range(1,11):
        for comb in combinations(range(0,10),i):
            comb=sorted(list(comb),reverse=True)
            li.append(int(''.join(map(str,comb))))
    li.sort()
    print(li[N])