백준 1174 줄어드는 수 파이썬

 

1174번: 줄어드는 수

 

조합 풀이

from itertools import combinations


N = int(input())
result = set()

for i in range(1, 11):
    for com in combinations(range(0, 10), i):
        com = sorted(com, reverse=True)
        result.add(int(''.join(map(str, com))))
result = sorted(result)

try:
    print(result[N - 1])
except IndexError:
    print(-1)

 

 

백트래킹 풀이

N = int(input())
result = set()
number = []


def dfs():
    if number:
        result.add(int(''.join(map(str, number))))
    for i in range(10):
        if not number or number[-1] > i:  # 왼쪽 수가 오른쪽 수 보다 크므로 감소 케이스에 해당
            number.append(i)
            dfs()
            number.pop()


dfs()
result = sorted(result)
print(result[N - 1] if len(result) >= N else -1)