동아리에서 DP를 배우면서 과제로 푼 '이진수 찾기'의 풀이 과정을 정리하고자한다.
처음에 문제를 딱 읽었을 때는 무슨 말인지 긴가민가 했다.
직접 써보면 간단하다.
만약 3자리 이진수 중, 2개 이하의 비트만 1인 것을 크기순으로 나열하면 다음과 같다.
000
001
010
011
100
101
110
이제 주어진 조건하에서 주어진 숫자 번째의 이진수를 찾아야한다.
처음에는 어떻게 풀어야할지 감이 안왔다.
그래서 예제 입력 1번 5 3 19 크기순으로 직접 나열해봤다.
00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
10000
.
.
.
근데 여기까지 쓰고보니 뭔가 규칙이 보인다.
위 사진처럼
00
01
10
11
이걸 반복해서 쓰고 있다.
이걸 자리수를 하나씩 늘려서 3자리 이진수로 묶어보고, 4자리 이진수로도 묶었을 때의 규칙을 보면
다음과 같은 규칙을 볼 수 있게 된다.
위의 예시의 경우
5자리 이진수 중 3개 이하의 비트를 1로 하는 모든 이진수의 개수는
첫번째 자리의 비트를 0으로 할 때 만들 수 있는 모든 숫자의 수
+
첫번째 자리의 비트를 1로 할 때 만들 수 있는 모든 숫자의 수
이를 규칙성을 보기 쉽게 바꿔쓰면 다음과 같이 쓸 수 있다.
4자리 이진수 중 3개 이하의 비트를 1로 하는 모든 이진수의 개수
+
4자리 이진수 중 2개 이하의 비트를 1로 하는 모든 이진수의 개수
첫번째 자리를 0으로 한다면 남은 4자리는 1을 최대 3개 쓸 수 있고,
첫번째 자리를 1로 한다면 남은 4자리는 1을 최대 2개 쓸 수 있다.
냅색 문제를 풀 때 떠올리는 아이디어와 비슷하다.
그리고 여기까지 나온 순간 이미 점화식이 세워져 버렸다ㅋㅋ
이제 N자리 이진수 중 M개 이하의 비트를 1로 하는 모든 이진수의 개수를
(N, M) 이라고 쓰도록 하자. (단, N >= M 이다.)
마치 조합을 보는 것 같은데, 파스칼 삼각형과 비슷한 느낌도 든다.
(이 문제 이항계수랑 관련있나?)
그러면
(N, M) = (N-1, M) + (N-1, M-1)
다음과 같은 식이 성립한다.
그리고 이 식으로부터 거꾸로 이진수를 찾아낼 수 있다.
그 이유는 (N-1, M) 이 유도된 과정이 맨 처음 자리수가 '0'일 때를 가정한 것이고,
(N-1, M-1)이 유도된 과정이 맨 처음 자리수가 '1'일 때를 가정한 것이기 때문이다.
그리고 우리는 이 이진수들을 크기순으로 정렬한 다음, 정렬된 이진수 중에서 특정 위치의 이진수를 찾는 것이 목적이다.
이해하기 쉽게 예제 입력 1을 기준으로 설명하면
(5, 3) = (4, 3) + (4, 2) 이다.
(4, 3) 이 의미하는게 무엇인가?
첫번째 자리는 0이라고 가정하고 나머지 4개의 자리만 볼 때,
4개중 최대 3개를 1로 할 수 있는 이진수들이다.
그럼 그 숫자는 무엇이 됐든 0 - - - - 의 형태이다.
같은 원리로 (4, 2)에 속하는 이진수들은
1 - - - -의 형태이다.
저 - - - -의 값에 상관없이
(4, 3) 에 속하는 이진수 < (4, 2)에 속하는 이진수 이다.
이분탐색을 떠올린다면 이제 풀이 법을 알 것이다.
만약 우리가 찾는 숫자가 (4, 3)에 속한다면
0 - - - - 의 형태이고
우리가 찾는 숫자가 (4, 2)에 속한다면
1 - - - - 의 형태이다.
따라서 (4, 3)의 값과 우리가 찾는 값을 비교하여
우리가 찾는 값이 더 크면 (4,2)에 속하는 수
우리가 찾는 값이 (4, 3)의 값과 같거나 작다면 (4, 3)에 속하는 수로 보고
첫번째 자리의 비트를 결정하면 된다.
이제 이 과정을 각 자리에 대해 반복하면 된다!
하지만 아직 처리하지 못한 부분이 있다.
첫번째로 N = M 일 때 어떻게 처리해야 할까?
간단하다.
2자리 이진수를 2개 이하의 1을 사용하여 모두 나타낸다면
00
01
10
11
사실상 모든 경우의 수를 적는 것과 같다.
그냥 2^N 개이다.
그리고 구조를 보면 첫번째 자리가 0인 이진수의 수와
첫번째 자리가 1인 이진수의 수가 같을 수 밖에 없다.
따라서 (N, N) = (N-1, N-1) + (N-1, N-1) 이다.
두번째로 M = 0 일 때 어떻게 처리하면 될까?
역시 간단하다.
2자리 이진수를 0개 이하의 1을 사용하여 모두 나타낸다면
00
하나 밖에 없다.
사실상 모든 자리수의 이진수에 대해서 똑같다. nCo 을 떠올려도 좋다.
따라서 (N, 0) = 0 이다.
따라서 이 2가지 특이 케이스와, 일반적인 케이스를 합쳐 점화식을 구성하면
다음과 같다.
마지막으로 이 알고리즘을 구현할 때는, DP테이블을 채우는 과정과 각 자리수를 결정하는 과정을 분리하여
따로 함수를 작성하였다.
# 2248 이진수 찾기
import sys
sys.setrecursionlimit(10**8)
def Fill_DP_Table(n_i, bit_i):
if bit_i == 0:
value = 1
elif n_i == bit_i:
if dp[n_i-1][bit_i-1] == -1:
value = Fill_DP_Table(n_i-1, bit_i-1)
value *= 2
else:
value = dp[n_i-1][bit_i-1]
else:
if dp[n_i-1][bit_i] == -1:
v1 = Fill_DP_Table(n_i-1, bit_i)
else:
v1 = dp[n_i-1][bit_i]
if dp[n_i-1][bit_i-1] == -1:
v2 = Fill_DP_Table(n_i-1, bit_i-1)
else:
v2 = dp[n_i-1][bit_i-1]
value = v1 + v2
dp[n_i][bit_i] = value
return value
def Print_Answer(n_i, bit_i, find, cnt):
if bit_i == 0:
if cnt < n:
print(0, end='')
Print_Answer(n_i, bit_i, find, cnt+1)
elif n_i == bit_i:
if dp[n_i-1][bit_i-1] < find:
find -= dp[n_i-1][bit_i-1]
print(1, end='')
else:
print(0, end='')
Print_Answer(n_i - 1, bit_i - 1, find, cnt+1)
else:
if dp[n_i-1][bit_i] < find:
find -= dp[n_i-1][bit_i]
print(1, end='')
Print_Answer(n_i-1, bit_i-1, find, cnt+1)
else:
print(0, end='')
Print_Answer(n_i-1, bit_i, find, cnt+1)
n, bit, find = map(int, input().split())
dp = [[-1 for _ in range(bit+1)] for _ in range(n+1)]
Fill_DP_Table(n, bit)
Print_Answer(n, bit, find, 0)자리수를 결정하는 함수(Print_Answer)에서 bit_i = 0 일 때 바로 0을 출력하는 이유는
bit_i = 0 이라는 의미 자체가 1을 사용할 수 없다는 뜻이기 때문이다.
따라서 DP테이블의 값을 따질 필요없이 0을 출력하면 된다.
'알고리즘 문제 > BOJ (Python3, C++)' 카테고리의 다른 글
| [BOJ][Python3] 5520 - The Clocks (0) | 2021.01.18 |
|---|---|
| [BOJ][Python3/PyPy3] 7579 - 앱 (0) | 2021.01.16 |
| [BOJ][Python3/PyPy3] 13904 - 과제 (0) | 2021.01.15 |
| [BOJ][Python3/PyPy3] 15553 - 난로 (0) | 2021.01.11 |
| [BOJ][Python3/PyPy3] 5639 - 이진 검색 트리 (0) | 2020.09.18 |
