백준 1038번 감소하는 수 | python | 백트래킹

문제

링크

풀이

⭐️ 경우의 수를 구할 때엔 반사적으로 백트래킹, 그리고 itertools 를 떠올리자 ⭐️

먼저 문제를 살펴보면,
음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면 그 수를 '감소하는 수'로 정의하고 있다. 예를 들어 321과 950은 감소하는 수지만, 322와 958은 아니다.

예시를 보면 알 수 있듯이 같은 숫자가 연속으로 나열되어 있어도 감소하는 수가 되지 못한다. 즉, 감소하는 수는 서로 다른 수들의 조합임을 알 수 있다.

문제에선 n이 주어졌을 때 n번째 감소하는 수를 구해야한다.
따라서 우리는,
1. for문을 돌며 모든 자릿수에 대하여 서로 다른 수들의 조합을 구한다.
2. 각 조합에 대하여 이때 내림차순 정렬을 진행한다. 또한 숫자로 저장해야 하므로 문자열을 정수화 시킨다.
3. 2번의 값을 answer 리스트에 더한다. answer는 '모든' 감소하는 수를 저장하는 리스트 변수이다.
4. 1~3을 반복문이 끝날때 까지 반복한다.
5. answer 리스트를 오름차순 정렬한다.
4. 리스트의 n번째 값을 뽑아낸다.

조합으로 풀이한다는 것만 캐치하면 이후로는 쉽게 풀이할 수 있다. 자세한 설명은 주석으로 대체하겠다.

import sys
from itertools import combinations

input = sys.stdin.readline
n = int(input())
answer = []

# 반복문을 통해 감소하는 수를 조합
# 최소 감소하는 수는 0, 최대 감소하는 수는 9876543210 
# 즉, 최소 자릿수 개수는 1, 최대 자릿수 개수는 10
for i in range(1, 11): # 자릿수에 맞게 1부터 10까지 반복
    for j in combinations(range(10), i): 
        num = sorted(list(j), reverse=True) # 감소하는 수이므로 reverse=True 하여 정렬 수행
        answer.append(int("".join(map(str, num))))

answer.sort()  # 결과 리스트 자체 정렬
print(answer[n] if len(answer) > n else -1)  # 감소하는 수가 있을 때와 없는 경우