[Python] 백준 1086 - 박성원

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

풀이

모든 순열을 따져봐야한다. N이 15밖에 안되므로, 단순이 모든 순열을 따져주면 되지 않나? 싶지만 15팩토리얼은 1,307,674,368,000이라는 큰 숫자다. 따라서 다른 방법을 찾아보자.

 

조금만 생각해보면 비트마스킹을 이용할 수 있다! $2^{15}$가 32,765이기 때문이다.

 

dp식을 다음과 같이 세워보자.

dp[mask][r] = 현재 상태에 있는 수들을 어떤 순서로 나열했을 때 만들어지는 수의 나머지가 r인 경우의 수

 

어떤 수를 이미 만들어진 수 뒤에 추가로 붙이면 나머지는 어떻게 변하는가?

예를들어 새로 붙일 수가 4자리 수라고 하자.

그러면 기존 수에 10,000을 곱하고 새로 붙일 수를 더하는 것과 마찬가지다.

그러면 나머지는 다음과 같이 변한다. (정수론적인 생각이 필요하다!)

 

((원래수를 K로 나눈 나머지 * 10,000을 K로 나눈 나머지) + 새로 붙이는 수를 K로 나눈 나머지) % K

 

이 사실을 이용해서 코드를 짤 수 있다.

 

from math import gcd
N = int(input())
num = []
l = []
for i in range(N):
    num.append(int(input()))
    l.append(len(str(num[i])))
K = int(input())

mod = [0]
for i in range(1, 51):
    mod.append(pow(10, i, K))

dp = [[0]*K for _ in range(1<<N)]
dp[0][0] = 1

#dp[mask][r] = 현재 상태에 있는 수들을 어떤 순서로 나열했을 때 만들어지는 수의 나머지가 r인 경우의 수
for mask in range(1<<N):
    for r in range(K):
        for i in range(N):
            next = mask | (1 << i)
            if next != mask:
                nextr = (r*mod[l[i]] + (num[i]%K)) % K
                dp[next][nextr] += dp[mask][r]

son = dp[(1<<N)-1][0]
mom = 1
for i in range(1, N+1):
    mom *= i
g = gcd(son, mom)
son //= g
mom //= g
print(f'{son}/{mom}')

 

대신 이렇게 하면 약간 최적화가 안돼서 실행시간이 2초정도 걸린다. (그래도 AC는 받는다.)

 

r 루프를 맨 안쪽으로 옮기고, next값을 모든 r과 i에 대해서 미리 계산해주는 방식으로 최적화를 해줄 수 있다. (그러면 한 300ms 안에 돌아간다.)

 

from math import gcd
import sys
input = sys.stdin.readline
N = int(input())
num = []
l = []
for i in range(N):
    num.append(int(input()))
    l.append(len(str(num[i])))
K = int(input())

mod = [0]
for i in range(1, 51):
    mod.append(pow(10, i, K))

dp = [[0]*K for _ in range(1<<N)]
dp[0][0] = 1

tmp = [[0]*K for _ in range(N)]

for i in range(N):
    for r in range(K):
        tmp[i][r] = (r*mod[l[i]] + (num[i]%K)) % K

#dp[mask][r] = 현재 상태에 있는 수들을 어떤 순서로 나열했을 때 만들어지는 수의 나머지가 r인 경우의 수
for mask in range(1<<N):
    for i in range(N):
        next = mask | (1 << i)
        if next != mask:
            for r in range(K):
                dp[next][tmp[i][r]] += dp[mask][r]

son = dp[(1<<N)-1][0]
mom = 1
for i in range(1, N+1):
    mom *= i
g = gcd(son, mom)
son //= g
mom //= g
print(f'{son}/{mom}')

 

비트필드에서의 DP를 확실히 이번기회에 제대로 경험해본 것 같다.

나머지로 dp를 관리해줄 생각이 어려웠다.