[Python/파이썬] 백준 1038번 감소하는 수

1038번: 감소하는 수

 

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

코드

n = int(input())

dec = set()


def bt(num):
    dec.add(int(num))
    for i in range(9, -1, -1):
        if i > int(num[0]):
            new_num = str(i) + num
            bt(new_num)
        else:
            break


for i in range(10):
    bt(str(i))

if n >= len(dec):
    print(-1)
else:
    print(sorted(list(dec))[n])

백트래킹을 이용하여 풀이하였다.

문자열 형태로 된 수(num)를 bt 함수의 인자로 받는다. for문을 돌며 9~0 중에서 그 수의 가장 앞자리 수보다 큰 숫자가 있다면 num 앞에 붙인 문자열을 new_num 변수에 저장하고, 이를 인자로 넘겨주며 bt를 재귀호출하였다. 

 

다 풀고 나서 다른 사람들의 풀이도 찾아보았는데 조합을 이용해서 푼 사람도 있다고 해서 조합으로 다시 풀어보았다.

from itertools import combinations

n = int(input())
dec = set()
for length in range(1, 11):
    for comb in combinations(range(10), length):
        comb = sorted(list(comb))
        num = 0
        for j in range(0, length):
            num += comb[j] * (10**j)
        dec.add(num)
if n >= len(dec):
    print(-1)
else:
    print(sorted(list(dec))[n])