[Python 3] BOJ - 12783 "곱셈 게임"

 # 문제 링크

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

12783번: 곱셈 게임

 

 # 풀이

 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 다이나믹 프로그래밍의 상태 공간을 현재 숫자가 num일 때 필요한 곱셈 카드의 최소 갯수인 dp[num]이라 정의한다. 만일, 어떤 수 k를 3개의 곱셈을 통해 만들 수가 있다면 $a_1 \ * \ a_2 * \ a_3 * a_4 = k$로 나타낼 수 있고, 각각의 수는 k의 약수가 됨을 알 수 있다.

<그림 1. k=20인 경우>

 위 그림 1의 경우는 k가 20이고 쓸 수 있는 카드가 1,0,2인 경우를 나타낸 그림이다. 위에서 약수인 수만 상태 전이가 가능하므로 20의 약수인 1,2,4,5,10,20이 다음 상태 공간이 된다. 첫번째로 1을 보면 1은 arr에서 나타낼 수 있으므로 상태 공간의 정의인 1을 만들기 위한 곱셈 카드의 최소 수는 0이다.

<그림 2. k=20인 경우>

 위 그림 2는 그림 1의 후속과정을 나타낸 그림이다. dp[2]의 경우 그림 1의 경우와 같기 때문에 0이 된다. 그런데 4는 현재 arr로는 만들 수 없으니 4의 약수들 중 가능한 수들로 구성해야만 한다. 그런데, 4의 약수인 1,2,4 중 1과 2는 이미 최소 곱셈 카드 수를 알고 있다. 따라서, 4를 만들려면 1과 4 혹은 2와 2를 통해 만들 수 있는데 현재 4 자체는 만들 수 없는 상태이기 때문에 2와 2를 통해서만 만들 수 있다. 그런데 약수 두 개로 현재 수를 만들려면 반드시 곱셈 카드가 하나는 필요하기 때문에 dp[4] = dp[2] + dp[2] + 1이 됨을 알 수 있다. 따라서, 점화식은 $dp[k] = min(dp[k], dp[i] + dp[j] + 1) \ if \ k \ mod \ i=0 \ and \ k \ mod \ j=0$이 됨을 알 수 있다.

<그림 3. k=20인 경우>

 위 그림 3은 위 그림 2의 후속과정을 나타낸 그림이다. 그림 2의 논리와 똑같이 계산하게 되면 5는 현재 arr을 통해 만들 수 없으므로 inf값이 된다

<끄림 4. k=20인 경우>

 위 그림 4는 그림 3의 후속과정을 나타낸 그림이다. 10의 경우는 현재 arr로 나타낼 수 있기에 0의 값을 갖는다. 이 때 마지막 dp[20]의 값을 구하려면, 위 그림 1~3의 논리대로 1이 됨이 알 수 있다. 그런데 실제로는 arr을 통해 20을 만들 수 있으므로 0이 되어야 한다. 따라서, 상태 공간에 처음 진입 시, 현재 수가 arr로 만들 수 있다면 inf값으로 초기화를 하는 것이 아니라 0으로 초기화를 해주어야 한다. 

<그림 5. 비트마스킹>

 위 그림 5는 현재 숫자를 arr의 원소들로 구성할 수 있는지 없는지를 비트마스킹으로 판별하는 그림이다. 1부터 1,000,000까지의 수를 key, 그 때 자릿수 숫자의 비트마스킹을 value를 갖는 딕셔너리를 미리 계산한 후, 현재 arr의 원소들로 이루어진 비트마스킹과 &연산을 했을 때, 현재 수의 비트마스킹이 나오게 된다면 현재 arr의 원소들로 해당 수를 만들 수 있음을 확인할 수 있다. 따라서, 좌측 그림의 경우는 실제 arr의 원소로 20을 만들 수 있고, 우측 그림의 경우는 실제 arr의 원소에 3이 없기 때문에 32를 만들 수 없다

 

 # 코드

import sys

# go : 현재 숫자가 num일 때 필요한 최소 곱셈 카드수를 리턴하는 함수
def go(num):
    # Memoization
    if dp[num] != -1:
        return dp[num]
    # 만일 현재 arr로 만들 수 있다면 0으로 초기화, 그렇지 않다면 무한대로 초기화
    dp[num] = 0 if bit & cache[num] == cache[num] else 9876543210
    for i in range(1, int(num ** 0.5) + 1):
        # 약수인 경우
        if num % i == 0:
            # 점화식
            dp[num] = min(dp[num], go(i) + go(num // i) + 1)
    return dp[num]

# cache : 1이상 1,000,000이하의 수를 key, 구성 숫자의 비트마스킹을 value로 갖는 딕셔너리
cache = dict()
for i in range(1, 1000001):
    temp = 0
    for j in str(i):
        temp |= (1 << int(j))
    cache[i] = temp

# 입력부
tc = int(sys.stdin.readline())
for _ in range(tc):
    n, *arr = list(map(int, sys.stdin.readline().split()))
    # bit : 현재 arr의 원소들로 만들어진 비트마스킹
    bit = 0
    for i in arr:
        bit |= (1 << i)
    m = int(sys.stdin.readline())
    for _ in range(m):
        k = int(sys.stdin.readline())
        dp = [-1] * (k + 1)
        res = go(k)
        # 조건에 따라 정답 출력
        print(res if res != 9876543210 else -1)