[백준/Python]1038: 감소하는 수

문제

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

백준 문제집 - 0x12강 - 수학

 

알고리즘: 수학, 백트래킹, 브루트포스

---

풀이

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

감소하는 수가 되려면 수의 왼쪽부터 오른쪽까지 내림차순이어야 한다.

예를들어,

11, 352, 901 → 감소하는 수 X

10, 521, 910 → 감소하는 수 O

 

따라서 0 ~ 9 의 숫자로 만들 수 있는 감소하는 수의 최댓값은 9876543210 이다.

즉 1자리부터 10자리까지 백트래킹 or 조합을 사용하여 감소하는 수를 생성하고, 리스트에 추가한다.

for i in range(1, 11):
    for j in combinations(range(9, -1, -1), i):
        num = "".join(list(map(str, list(j))))
        ret.append(int(num))

combinations 모듈을 사용하면 참조할 리스트의 첫번째 원소부터 순서대로 조합을 생성하므로, 98, 97... 87, 86... 순으로 자연스럽게 감소하는 수 형태를 띄게 된다.

 

모두 구했다면 리스트를 오름차순으로 정렬 후 리스트의 길이가 N 이상이라면 -1을, 아니라면 N번째 값을 출력한다.

잘 보면 감소하는 수의 순번을 1부터 계산하는것이 아닌 0부터 계산하기 때문이다.

만약 8번째 감소하는 수를 구하고자 하는데 리스트가 아래와 같이 구성되어있다고 생각해보면,

ret = [0, 1, 2, 3, 4, 5, 6, 7]

리스트의 길이가 8이지만 조건을 만족하지 못한다.

따라서 리스트의 길이가 최소 N + 1일경우에만 N번째 감소하는 수를 구할 수 있다.

 

전체 코드

1. combinations 모듈 사용

# 메모리: 32412KB / 시간: 36ms
from itertools import combinations


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

for i in range(1, 11):
    for j in combinations(range(9, -1, -1), i):
        num = "".join(list(map(str, list(j))))
        ret.append(int(num))

ret.sort()
if N >= len(ret):
    print(-1)
else:
    print(ret[N])

 

2. 백트래킹 사용

# 메모리: 32412KB / 시간: 40ms
N = int(input())
ret = []

def dfs(comb, last, length):
    if len(comb) == length:
        ret.append(int("".join(map(str, comb))))
        return
    
    for i in range(last-1, -1, -1):
        comb.append(i)
        dfs(comb, i, length)
        comb.pop()

for length in range(1, 11):
    dfs([], 10, length)

ret.sort()
print(ret[N] if N < len(ret) else -1)