[백준 1562] 계단 수 - 비트필드를 이용한 DP (파이썬 Python)

계단 수 

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력

10

예제 출력

1

---

'그냥' 계단수 구하기

이 문제와 유사한 쉬운 계단 문제가 있는데 여기 방식에서 0~9까지의 숫자가 들어가있는지만 체크하면됩니다.

쉬운 계단 문제에서는 그냥 n자리가 나왔을때, 그냥 계단 수만 구하면 되므로,

다이나믹프로그래밍(DP)를 이용해서 DP[i][j]를 아래와 같이 정의를 해서 풀 수 있습니다.

길이가 k인 계단수를 구하고, k+1의 계단수를 기존 길이k인 계단수에다가 최고자리에 수 하나씩 추가해서 계단수를 구하는 방식 입니다.

dp[i][j] i = 자리 수, j = 맨 뒷자리에 오는 수
j = 0 일 때, dp[i][j] = dp[i-1][1]
1<= j <=8 일 때, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
j = 9 일 때, dp[i][j] = dp[i-1][8]

예를 들어, 최고자리가 4이거나 6인(차이가 1만 나는) n-1 자리의 계단수에다가 최고자리 앞에 5만 붙이면 5가 들어가는 n자리 계단수가 완성입니다.

최고자리가 4이거나 6인(차이가 1만 나는) n-1 자리의 계단수의 경우의 수를 더하면  5가 들어가는 n자리 계단수의 경우의 수가 나옵니다.

---

필드를 하나 추가하면 ?

이렇게 하면 쉬운 계단 문제는 풀 수 있는데, 문제는 이 하나하나 계단수에 대해서 0~9까지 어느정도 포함되어있는지도 따로 분류를 해야된다는 것입니다.

같은 최고자리가 5인 n자리의 계단수라도, 어떤 계단수는 1,2,3,4,5를 포함하고, 어떤 계단수는 5,6,7,8,9를 포함하고, 어떤 계단수는 0~9까지 전부포함하는 완벽한 계단수도 있는등 여러가지 다 분류를 해서 경우의 수를 만들어야된다는 것입니다.

 

추가로 분류를 해야되는 DP(다이나믹프로그래밍)에서는 보통 '필드'를 하나 더 추가합니다.

dp[i][j][k] 이런씩으로요!

k에는 0~9까지 어떤 수가 포함되어있는지 정보를 입력해야되는데 어떻게 수의 집합을 정수로 정의 할 수 있을까요....

집합을 이진수로 표현해서 연산하는 방법이 있습니다! 그것이 비트마스킹이고, 비트마스크 수를 이용해서 필드를 추가하는것이 비트필드를 이용한 다이나믹프로그래밍 입니다!

---

비트필드

b를 이진수 체계로 해서 각 이진수 자릿수 마다 해당 수의 존재 여부를 0 또는 1로 표현하면 됩니다.

45656이란 계단 수에서 0~9까지의 수 사용여부를 비트로 나타내면 아래와 같습니다.

총 4,5,6이란 수가 쓰였으므로 총 0b0001110000(파이썬에서 이진수 표시방식)이란 이진수가 나오고 이 정수를 세번째 필드의 인덱스로 사용하면 됩니다!

사용할 수 있는 숫자들	9	8	7	6	5	4	3	2	1	0
이 계단수에 존재여부	0	0	0	1	1	1	0	0	0	0

 

모든 탐색이후 0~9를 다 포함하는 계단수를 구하려면 세번째 필드의 인덱스가 0b1111111111(1023)인 DP테이블에서 경우의 수를 가져와야겠죠?

---

비트마스킹

이런 비트필드를 이용해서 집합연산하는 등의 알고리즘을 비트마스킹이라고 합니다.

여러 집합 연산들이 많지만, 이 문제에서 필요한 연산만 설명하겠습니다.

 

0~9까지 숫자여부를 체크하려면 필드의 크기는 10이 되어야하므로 아래와 같이 설정하면 됩니다.

S = 0b0000000000

---

원소 추가

S에 num을 추가한다면, S의 num번 비트만 1을 만들어주면 됩니다.

(1 << num)은 num번째를 1로 설정주는 것으로,1 * 2^num 라고 생각해주면 됩니다. 1이란 비트를 num번 왼쪽으로 옮기는 거죠(num번 2를 곱함)

OR 연산을 해주면  num번째 1이 기존과 합집합이 되므로, 이미 있으면 아무일도 안일어나고, 존재하지 않았다면 num번째자리에 필드가 1이 추가되게 됩니다.

S |= (1 << num)

---

원소 삭제

S에서 num을 제거한다면, S의 num번 비트를 0으로 만들어주면 됩니다.

~은 not연산자로 모든 비트를 반전시킵니다.

~(1 << num)는 num번 비트만 0으로 만들고 나머지는 1로 만들어 주므로, 이것을 and연산자로 해주면 num번째가 0으로 바뀝니다.

S &= ~(1 << num)

---

전체집합

1000 - 1 = 999가 되듯이, 총길이가 10인 이진수를 0b1111111111로 만들고 싶으면 길이가 하나 더 긴 (1<<10)에 대해서 -1을하면, 자리수가 10으로 한칸 줄어드고 나머지 비트가 1로 반전됩니다.

이 문제에서는 1023이 되고, 총 필드의 인덱스는 0~1023으로 총 1024가지를 표현할 수 있습니다.

S = (1 << 10) - 1

---

비트필드를 추가한 DP

dp[자리 수][마지막 숫자][사용된 숫자들의 비트 값]

1~8까지에 수는 아래 두식 둘다 만족합니다.

마지막 숫자가 0보다 크면
dp[자리 수 + 1][마지막 숫자 - 1][사용된 숫자들의 비트 값 | 1 마지막 숫자 - 1] += dp[자리 수][마지막 숫자][사용된 숫자들의 비트 값]
마지막 숫자가 9보다 작으면
dp[자리 수 + 1][마지막 숫자 + 1][사용된 숫자들의 비트 값 | 1 마지막 숫자 + 1] += dp[자리 수][마지막 숫자][사용된 숫자들의 비트 값]

 

---

파이썬(Python) 코드

위에 DP 점화식을 그대로 옮기면 됩니다.

import sys
input = sys.stdin.readline
n = int(input())
num_range = 10 # 0~9
bit_range = 1 << num_range # 9876543210 (0b0 ~ 0b1111111111) -> total 1024 (1023까지)
MOD = 10**9;
DP = [[[0]*(bit_range) for _ in range(num_range)] for _ in range(n+1)]

# 한자리 수 부터 시작하려면 한자리수들 다 1로 초기화
# 1 예시 0b0000000010
for k in range(num_range):
  DP[1][k][1<<k] = 1

for i in range(1,n): # n-1까지하면 n 구할수 있음
  for j in range(num_range):
    for b in range(bit_range):
      if 0<=j<9:
        more = b | 1<<(j+1)
        DP[i+1][j+1][more] += DP[i][j][b]
        DP[i+1][j+1][more] %= MOD
      if 0<j<=9:
        less = b | 1<<(j-1)
        DP[i+1][j-1][less] += DP[i][j][b]
        DP[i+1][j-1][less] %= MOD

total = 0
for k in range(1,num_range): # 0으로 시작하는 수만 제외
  total += DP[n][k][0b1111111111]
  total%=MOD
print(total)