백준 9029번 정육면체

문제

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에 대해서도 동일하게 적용된다.

문제풀이

사용한 알고리즘 : DP

(1) 코드 6

 ' dp[w][l][h] : w l h 상태에서 최소 절단으로 만들어지는 조각 수' 라고 설정하였습니다.

(2) 코드 8~34

 dp를 top down 으로 구현하는 함수를 짜주었습니다.

 기저는 W=L=H 일때 1을 리턴하고, 

 셋 중 하나의 길이가 1일 경우 다른 두 변을 곱한 값을 리턴합니다.

(3) 코드 15~23

 W, L, H 에 직각으로 짜르는 모든 경우를 다 해봅니다. 

(4) 코드 26~31

 정육면체를 어떻게 돌려도 같은 정육면체임을 생각해줍니다.