[백준 1493 / JAVA] 박스 채우기

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

1493번: 박스 채우기

 

박스를 어떻게 나눠야하는지 생각하는 것이 어려웠다.

박스에 넣을 수 있는 가장 큰 큐브를 넣은 후 오른쪽, 왼쪽, 위 3가지로 남은 공간을 나누어 다시 재귀 호출하는 분할 정복 방식을 이용했다.

    public static void sol(int l, int w, int h) {
        if (l == 0 || w == 0 || h == 0)
            return;

        int powd;

        if (flag == false)
            return;

        int min;
        min = Math.min(l, w);
        min = Math.min(min, h);

        // 넣을 수 있는 가장 큰 큐브 길이
        d = checkMin(logB(min, 2));

        // 못 넣는다면
        if (d == -1) {
            flag = false;
            return;
        }

        result++;
        powd = (int) Math.pow(2, d);

        sol(l, w, h - powd);
        sol(l, w - powd, powd);
        sol(l - powd, powd, powd);
    }

만약 한 변이라도 0이라면 큐브를 넣을 수 없다.

flag는 큐브를 다 채우지 못하는지 확인하는 변수이다.

세 모서리 중 가장 길이가 작은 모서리를 기준으로 넣을 수 있는 가장 큰 큐브 길이를 구한다.

 

    public static int checkMin(int d) {
        for (int i = N - 1; i >= 0; i--) {
            if (cube[i][0] <= d && cube[i][1] > 0) {
                cube[i][1]--;
                return cube[i][0];
            }
        }
        return -1;
    }

넣을 수 있는 가장 큰 큐브 길이를 구하는 메서드이다.

입력받은 길이와 일치하며 큐브가 남아있는 경우 해당 길이를 반환하고 없다면 -1을 반환한다.

 

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int length, width, height, N, d, result = 0;
    static int[][] cube;
    static boolean flag = true;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input;
        StringTokenizer st;

        input = br.readLine();
        st = new StringTokenizer(input);

        length = Integer.parseInt(st.nextToken());
        width = Integer.parseInt(st.nextToken());
        height = Integer.parseInt(st.nextToken());

        N = Integer.parseInt(br.readLine());
        cube = new int[N][2];
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            st = new StringTokenizer(input);
            cube[i][0] = Integer.parseInt(st.nextToken());
            cube[i][1] = Integer.parseInt(st.nextToken());
        }

        sol(length, width, height);
        if (flag == false)
            System.out.println(-1);
        else
            System.out.println(result);

    }

    public static void sol(int l, int w, int h) {
        if (l == 0 || w == 0 || h == 0)
            return;

        int powd;

        if (flag == false)
            return;

        int min;
        min = Math.min(l, w);
        min = Math.min(min, h);

        // 넣을 수 있는 가장 큰 큐브 길이
        d = checkMin(logB(min, 2));

        // 못 넣는다면
        if (d == -1) {
            flag = false;
            return;
        }

        result++;
        powd = (int) Math.pow(2, d);

        sol(l, w, h - powd);
        sol(l, w - powd, powd);
        sol(l - powd, powd, powd);
    }

    public static int logB(int x, int y) {
        return (int) (Math.log10(x) / Math.log10(y));
    }

    public static int checkMin(int d) {
        for (int i = N - 1; i >= 0; i--) {
            if (cube[i][0] <= d && cube[i][1] > 0) {
                cube[i][1]--;
                return cube[i][0];
            }
        }
        return -1;
    }
}

 

문제는 속도가 너무 나오지 않는다 다른 코드들을 보면서 어느 부분이 잘못되었는지 확인해야겠다.