[백준 1086번] 박성원 (Python3)

import sys,math
input = sys.stdin.readline

def DFS(k,bit,l):
  DP[k][bit] = 0
  if bit == (1<<N)-1:
    DP[k][bit] = int(not k)
    return
  for n in range(N):
    if bit&(1<<n):
      continue
    k1 = (k+remain[n]*remain10[l])%K
    if DP[k1][bit|(1<<n)]==-1:
      DFS(k1,bit|(1<<n),l+length[n])
    DP[k][bit] += DP[k1][bit|(1<<n)]

N = int(input())
data = [int(input()) for i in range(N)]
K = int(input())
remain,length = [n%K for n in data],[len(str(n)) for n in data]
remain10 = [10**i%K for i in range(750)]

DP = [[-1]*(1<<N) for i in range(K+1)]
DFS(0,0,0)
numer,denom = DP[0][0],math.factorial(N)
if not numer:
  denom = 1
else:
  for p in range(2,int(math.sqrt(numer))+1):
    while numer%p == denom%p == 0:
      numer //= p
      denom //= p
  if numer != 1:
    if not denom%numer:
      denom //= numer
      numer = 1
print(str(numer)+"/"+str(denom))

어려운 문제였다. 비트마스킹 + DP로 해결하였다.

 

꽤 오랫동안 풀지 못했던 문제였다. 그런데 사실 풀지 못했던 가장 큰 이유는 문제를 잘못 읽어서였다. 임의의 숫자를 뽑아서 순열을 만드는 경우의 수를 구하는 문제인 줄 알았는데, 알고보니 모든 숫자를 전부 사용해서 만드는 순열의 경우의 수를 고르는 문제였다. 

 

알고리즘을 설명하면,

1. DP를 2^N * K개의 배열로 둔다. DP[k][bit]는 bit에 포함된 숫자들을 사용하여 나머지가 k일 때, bit에 포함되지 않은 숫자들을 붙여서 K로 나누어떨어지는 수를 만드는 개수를 의미한다.

2. 다음 숫자를 붙일 때 나머지는 (현재 나머지 + 10^(현재길이)+다음숫자) %K와 같다.

3. 숫자를 구한 뒤, 기약분수로 만들어 출력한다.

 

이때, 2번 과정에서 현재 길이, 현재 길이에 대한 나머지, 다음 숫자에 대한 나머지를 빠르게 구할 수 있도록 미리 리스트를 만들어두는 것이 좋다. (remain,length,remain10 참고) 이걸 안했더니 시간초과가 발생하였다.

 

 

오늘의 교훈) Top-down 방식 말고 bottom-up 방식도 고려하자