[Python] 1038번 감소하는 수

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

1038번: 감소하는 수

---

 

24/01/16

 

 

백트래킹 혹은 브루트 포스로 구현할 수 있는 유명한 문제이다.

 

비트마스킹을 이용해 구현하는 색다른 방법을 발견하여 적어보고자 한다.

 

---

 

기존 문제 접근 방식:

 

 

처음 문제를 접근했을 때에는 문제의 조건을 만족하는 함수 bruteforce를 작성했었다.

 

이 함수는 재귀적으로 호출을 하는 함수로, 호출을 받을 때마다 인자로 받은 현재 숫자를 리스트에 추가하고, 조건을 만족하도록 그 다음 숫자를 재귀적으로 다시 호출하는 함수다.

 

이 함수는 수의 첫 번째 숫자와 그 수, 그리고 그 수의 길이를 인자로 입력받는다.

 

감소하는 수를 만드려면 새로 만드는 수는 기존 수의 첫 번째 숫자보다 더 커야 한다.

 

이를 만족하기 위해 for문을 사용하여 재귀 호출을 해주었다.

 

맨 처음으로 한 자리 수 $i$를 인자로 넣으면, bruteforce 함수를 통해 추가되는 수들은 모두 $i$가 수의 일의 자리에 오는 수들이므로, 우리는 bruteforce함수 자체를 10번 반복하면 모든 감소하는 수들을 추가할 수 있다.

 

이후 정렬 함수를 통해 정렬하여, 감소하는 수가 크기 순으로 정렬되도록 하였다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 1038번 감소하는 수
# 브루트포스
import sys
input = sys.stdin.readline

number_list = []
def bruteforce(first_digit, num, num_len):
    number_list.append(num)
    for i in range(first_digit+1, 10):
        new_num = i*(10**num_len) + num
        bruteforce(i, new_num, num_len+1)
    return
for i in range(10):
    bruteforce(i, i, 1)
number_list.sort()
N = int(input())
if N >= len(number_list):
    print(-1)
else:
    print(number_list[N])

---

 

이후의 접근 방식:

 

 

비트 마스킹을 이용한 접근 방식을 알고 난 후에 이 문제를 다시 풀어보았다.

 

우리는 결국 $0$부터 $9$까지의 숫자들을 사용하거나, 사용하지 않음으로써 감소하는 수를 만든다.

 

그리고 특정 숫자들을 사용한, 예를 들자면 $3, 4, 9$를 사용한 감소하는 수는 오직 하나 밖에 존재하지 않는다는 사실을 잘 알고 있다.

 

따라서, 우리는 $0$부터 $9$까지의 숫자 사용 여부 하나에 감소하는 수 하나를 대응시킬 수 있다.

 

$0$부터 $9$까지의 숫자 사용 여부 하나는 각 숫자마다 하나의 비트를 대응하여, 사용하였다면 비트를 키는 것으로, 사용하지 않았다면 비트를 끄는 것으로 생각할 수 있다.

 

$0$부터 $9$까지 $10$개의 숫자에 대한 비트를 사용하므로, $0$부터 $2^{10}$직전까지의 숫자 하나하나로 비트마스킹을 진행할 수 있다.

 

따라서 감소하는 수는 총 $2^{10}$개가 존재하며, 이를 넘어가는 범위라면 $-1$을 출력하고, 그렇지 않는다면 비트마스킹을 이용해 추가된 감소하는 수를 출력하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1038번 감소하는 수
# 브루트포스
import sys
input = sys.stdin.readline

number_list = []
for i in range(1 << 10):
    num = bin(i)[2:]
    number = 0
    for j in range(len(num)):
        if num[j] == '1':
            number *= 10
            number += (len(num) - j - 1)
    number_list.append(number)
number_list.sort()
N = int(input())
if N+1 >= len(number_list):
    print(-1)
else:
    print(number_list[N+1])