BOJ - 정육면체 9029번 (JAVA)

❓ 문제 - 백준 정육면체 9029번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/9029)

9029번: 정육면체

 

 

 

📝 문제해결법

1. 문제

• 원목의 가로, 세로, 높이의 길이가 W, L, H일 때 원목을 가로, 세로, 높이 방향으로 자르는 작업을 정육면체가 될 때까지 반복적으로 자르는데 걸리는 최소 횟수를 출력한다.

 

2. 해결 방법

• 우선 DP를 통해 문제를 해결해야 한다. 소스코드에서 box 3차원 배열을 선언하여 특정 w, l, h일때 모든 나무조각을 정육면체로 될 때까지의 최소 절단 회수를 저장한다.
• 만약 h를 기준으로 절단 할 때 i만큼 자르면 w, l, i 와 w, l, h-i로 나누어진다. 이 때, w, l, h를 w, l, i의 최소 절단 횟수와 w, l, h-i 절단 횟수의 합으로 구해질 수 있으며, 이것은 w, h, l 방향 모두 시도한다.
• 그리고 w, l, h의 길이중 하나가 1일 경우에는 다른 두 변을 곱한 값을 배열에 저장한다.
• 또한 w, l, h의 길이 중 두 길이가 나머지 하나의 배수인 경우 또한 나눈 형태의 값으로 값을 배열에 저장한다.
• 나머지는 경우는 이제 자르는 모든 경우를 dp를 활용해서 최소 절단 횟수를 구한다.

 

 

3. 느낀점

• DP 문제를 풀려고 할 때 쫄지말자.. 생각보다 풀이가 간단할 수도 있다...!!!!!!!!!!!!!!!!!!!

 

 

 

💻 소스코드 (JAVA)

// BOJ - 정육면체(9029번)
// DP
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_9029 {
    public static int[][][] box;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int TC = Integer.parseInt(br.readLine());
        box = new int[201][201][201];

        for(int w=1;w<=200;w++){
            for(int l=1;l<=200;l++){
                for(int h=1;h<=200;h++){
                    if(box[w][l][h] == 0){
                        if(w == 1){
                            box[w][l][h] = l*h;
                        } else if(l == 1){
                            box[w][l][h] = w*h;
                        } else if(h == 1){
                            box[w][l][h] = w*l;
                        } else if((l % w == 0) && (h % w == 0)){
                            box[w][l][h] = (l / w) * (h / w);
                        } else if((w % l == 0) && (h % l == 0)){
                            box[w][l][h] = (w / l) * (h / l);
                        } else if((w % h == 0) && (l % h ==0)){
                            box[w][l][h] = (w / h) * (l / h);
                        } else {
                            box[w][l][h] = Integer.MAX_VALUE;
                            for(int i=1;i<=w/2;i++){
                                box[w][l][h] = Math.min(box[w][l][h], box[i][l][h] + box[w-i][l][h]);
                            }

                            for(int i=1;i<=l/2;i++){
                                box[w][l][h] = Math.min(box[w][l][h], box[w][i][h] + box[w][l-i][h]);
                            }

                            for(int i=1;i<=h/2;i++){
                                box[w][l][h] = Math.min(box[w][l][h], box[w][l][i] + box[w][l][h-i]);
                            }
                        }

                        box[w][h][l] = box[w][l][h];
                        box[h][l][w] = box[w][l][h];
                        box[h][w][l] = box[w][l][h];
                        box[h][l][w] = box[w][l][h];
                        box[w][l][h] = box[w][l][h];
                        box[w][h][l] = box[w][l][h];
                    }
                }
            }
        }


        for(int test_case=1;test_case<=TC;test_case++){
            st = new StringTokenizer(br.readLine(), " ");
            int w = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

            System.out.println(box[w][l][h]);
        }
    }