[BOJ] 1493. 박스 채우기

[작성일]

• 2022-03-10

[분류]

• 그리디
• 분할정복
  
  
  

[문제링크]

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

[요구사항]

• 필요한 큐브의 개수의 최솟값을 출력한다. 만약 채울 수 없다면 -1을 출력한다.
  
  
  

[풀이]

그리디와 분할정복의 개념을 적용하여 푸는 문제이다.
핵심은 가장 큰 큐브부터 가장 작은 큐브까지 넣어가면서 갯수를 구하는 것이다.
가로, 세로, 높이를 각각 현재 큐브 가로, 세로, 높이로 나누고 모두 곱하면 들어갈 수 있는 큐브의 갯수가 된다.
이후, 쓸 수 있는 큐브 갯수랑 min 연산을 해서 보정을 해준다.
이를 반복하면서 진행하게된다.

이 때 이전까지 쌓인 큐브 개수에 8을 곱해주면서 진행하게 되는데 그 이유는 이전 큐브가 8배 더 크기 때문에 지금 큐브단위로 바꿔주려면 8을 곱해야 맞기 때문이다.

이렇게 반복한 후, 마지막에 총 크기와 처음에 주어진 가로, 세로, 높이의 곱이 동일한 경우에 꽉 채울 수 있다는 의미이기 때문에 구한 총 개수를 출력해주고, 아닐 경우에는 -1을 출력한다.

[코드]

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

class Main {
    static long L, W, H;
    static int N;
    static long[] cube;

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

        L = Long.parseLong(st.nextToken());
        W = Long.parseLong(st.nextToken());
        H = Long.parseLong(st.nextToken());
        N = Integer.parseInt(br.readLine());

        cube = new long[N];
        int a;
        long b;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Long.parseLong(st.nextToken());
            cube[a] = b;
        }

        // 제일 큰 큐브부터 시작해서 박스를 나눠보면서 가능하지 보기
        long cubeLen = (1L << N - 1);
        long sum = 0;
        long before = 0;
        for (int i = N - 1; i >= 0; i--) {
            // 다음 큐브 사이즈로 채울 때 2x2x2 만큼 작아지기 때문에 전체 갯수가 8배로 증가하는 걸 고려
            before *= 8;

            // 지금 큐브사이즈로 채울 수 있는 숫자에서 이전꺼 만큼은 빼줘서 값을 구한다.
            long value = (L / cubeLen) * (W / cubeLen) * (H / cubeLen) - before;
            value = Math.min(cube[i], value);

            sum += value;
            before += value;
            cubeLen >>= 1L;
        }

        if (before == L * W * H) {
            System.out.println(sum);
        } else {
            System.out.println(-1);
        }
    }
}