[백준] 10881: 프로도의 선물 포장 - JAVA

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

 

풀이

세 개의 선물을 한 상자에 넣어 포장해야 한다.

 

선물 세 개를 상자에 넣는 방법은 두 가지 경우로 생각해볼 수 있다.

 

`ABC` 처럼 일렬로 놓는 방법과

 

A와 B를 위아래로 쌓고, C를 옆에 놓는 방법이 있다.

 

순열을 구해 3개의 선물의 순서를 구한다.

 

가로, 세로 길이가 주어진 선물을 그대로 놓을지 회전시켜 놓을지 `pos`배열에 저장하면서 순열을 구했다.

 

선물들의 순서와 회전여부가 주어지면 놓는 방법 2가지 경우에 필요한 상자의 크기를 구해 정답을 갱신했다.

 

---

 

메모리: 28108KB
시간: 352ms
언어: Java 11

import java.io.*;
import java.util.*;

public class Main {
    static class Present {
        int width;
        int height;

        public Present(int w, int h) {
            this.width = w;
            this.height = h;
        }
    }

    static Present[] list;
    static int result;
    static boolean[] visited, pos;
    static int[] sel;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int tc = 0; tc < t; tc++) {
            list = new Present[3];
            for (int i = 0; i < 3; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                list[i] = new Present(a, b);
            }

            result = Integer.MAX_VALUE;

            visited = new boolean[3];
            pos = new boolean[3];
            sel = new int[3];
            permutation(0);

            sb.append(result).append("\n");
        }

        System.out.println(sb.toString());
    }

    private static void permutation(int cnt) {
        if (cnt == 3) {
            calculation1();
            calculation2();
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (visited[i]) {
                continue;
            }
            sel[cnt] = i;
            visited[i] = true;
            pos[cnt] = true;
            permutation(cnt + 1);
            pos[cnt] = false;
            permutation(cnt + 1);
            visited[i] = false;
        }
    }

    private static void calculation2() {
        int width = 0;
        int height = 0;

        for (int i = 0; i < 2; i++) {
            int idx = sel[i];
            if (pos[i]) {
                width = Math.max(width, list[idx].width);
                height += list[idx].height;
            } else {
                width = Math.max(width, list[idx].height);
                height += list[idx].width;
            }
        }

        if (pos[2]) {
            width += list[sel[2]].width;
            height = Math.max(height, list[sel[2]].height);
        } else {
            width += list[sel[2]].height;
            height = Math.max(height, list[sel[2]].width);
        }

        result = Math.min(result, width * height);
    }

    private static void calculation1() {
        int width = 0;
        int height = 0;

        for (int i = 0; i < 3; i++) {
            int idx = sel[i];
            if (pos[i]) {
                width += list[idx].width;
                height = Math.max(height, list[idx].height);
            } else {
                width += list[idx].height;
                height = Math.max(height, list[idx].width);
            }
        }

        result = Math.min(result, width * height);
    }

}