WoodArt 사는 나무를 이용하여 여러 가지 조각품을 만드는 회사로 유명하다. 이 회사에서 일하는 세계적인 조각가 Mr. Kube 씨는 요즘 다양한 크기의 정육면체의 나무 조각들만을 이용하여 멋진 조형물을 만들기 위해 많은 시간을 투자하고 있다.
WoodArt 사에 공급되는 원목은 가로, 세로, 높이의 길이가 각각 W, L, H 인 직육면체인데, Mr. Kube 씨는 우선 이 원목을 잘라 모든 조각이 정육면체가 되도록 만든다. 나무를 정교하게 자르기 위해 그는 한 순간에 나무 한 조각을 잘라 두 개의 직육면체를 얻는다. 즉, 원목을 잘라 두 개의 직육면체를 얻고, 그 각각의 직육면체를 다시 자르는 작업을 반복하여 모든 나무 조각이 정육면체가 될 때까지 자른다. 그런데, 그는 직육면체의 원목을 받아 모든 조각이 정육면체가 될 때까지 절단하되, 절단 회수를 최소로 하길 원한다.
원목의 크기를 나타내는 W, L, H 값들은 각각 1 이상 200 이하의 정수이며, 최종적으로 얻어진 모든 정육면체의 한 변의 길이도 1 이상인 정수가 되도록 절단한다.
나무를 자르는 과정에서 발생할 수 있는 길이의 손실은 무시하기로 한다. 아래 그림에서 보인 것처럼, 자르기 전의 나무 조각의 크기가 W, L, H 이고, 절단한 후 두 조각의 크기가 각각 W, L, H1과 W, L, H2라면 H = H1 + H2 라고 가정한다. W와 L에 대해서도 동일하게 적용된다.
입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20) 가 주어진다. 각 테스트 케이스에 대해 원목의 크기를 나타내는 W,L,H (1 ≤ W, L, H ≤ 200) 값이 한 줄에 주어진다.
출력
출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해, 절단 횟수를 최소로 하여 자를 경우 생성되는 정육면체 조각들의 개수를 한 줄에 출력한다.
입력 예시
3
15 5 5
2 4 3
5 6 6
출력 예시
3
10
13
풀이
간단한 DP문제인데... 너무 간단해서 어렵게 생각했던 문제이다. 제한 시간이 10초임을 눈여겨본다면, O(N^4) 시간복잡도로도 충분히 도전해봄직하다.
가로 - 세로 - 높이가 같은 경우 : 이 경우는 그대로 정육면체를 만족하므로 1이 답이다.
가로, 세로, 높이 중 하나가 다른 둘을 나눌 수 있을 경우 : 이 경우는 기준이 되는 나눈 값이 한 변인 정육면체로 구성할 수 있다.
그 외의 경우 :
가로, 세로, 높이가 W, L, H일 때, 최소 경우의 수가 DP[W][L][H]라고 하자.
그렇다면 가로, 세로, 높이 관점에서 각각 둘로 나누었을 때의 DP값의 합중 최솟값이 그 값이 될 것이다.
이 때, 가로, 세로, 높이가 바뀌는 경우를 동시에 업데이트하여 실제 연산량을 더 줄여볼 수 있다.
풀이 코드
import sys
input = sys.stdin.readline
MAX = float('inf')
dp = [[[MAX for k in range(201)] for i in range(201)] for j in range(201)]
for i in range(1, 201) :
for j in range(1, 201) :
for k in range(1, 201) :
if dp[i][j][k] < MAX :
continue
if i == j == k :
dp[i][j][k] = 1
elif i % k == j % k == 0 :
dp[i][j][k] = (i // k)*(j // k)
elif i % j == k % j == 0 :
dp[i][j][k] = (i // j)*(k // j)
elif j % i == k % i == 0 :
dp[i][j][k] = (j // i)*(k // i)
else :
for l in range(1, max(i, j, k) // 2 + 1) :
if l <= i // 2 :
dp[i][j][k] = min(dp[i][j][k], dp[l][j][k] + dp[i-l][j][k])
if l <= j // 2 :
dp[i][j][k] = min(dp[i][j][k], dp[i][l][k] + dp[i][j-l][k])
if l <= k // 2 :
dp[i][j][k] = min(dp[i][j][k], dp[i][j][l] + dp[i][j][k-l])
dp[i][k][j] = dp[j][i][k] = dp[j][k][i] = dp[k][j][i] = dp[k][i][j] = dp[i][j][k]
def solve() :
W, L, H = map(int, input().split())
print(dp[W][L][H])
for _ in range(int(input())) :
solve()
