[BOJ] 백준 1493번 : 박스 채우기 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/1493

1493번: 박스 채우기

 

 

문제

세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱 꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...)

 

세준이가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필요한 큐브의 최소 개수를 출력하는 프로그램을 작성하시오.

 

 

풀이

그리디 알고리즘을 활용하는 문제였습니다. 처음에는 전체 부피를 구하고, 주어진 큐브의 부피를 큰 순서대로 넣어보는 식으로 로직을 짰었습니다. 하지만, 부피만 가지고 계산하면 치명적인 오류가 있었습니다.

 

가령, 박스의 길이가 3 X 4 X 8일 경우 부피는 96이고, 이 곳에 4 X 4 X 4 큐브를 넣는다고 가정해 봅시다.

 

부피만 계산하면, 4 X 4 X 4 큐브는 64라서 가능할 것처럼 보이지만, 실제로 생각을 해보면 큐브가 박스에 넣는 것은 불가능한 것을 알 수 있습니다.

 

그렇다면, 이 문제를 어떻게 해결할 수 있을까요?

 

바로, 박스 자체를 2^n x 2^n x 2^n으로 분할해 보면서 가지고 있는 큐브를 집어 넣어보는 것입니다. 아래 예제와 소스코드를 통해 이해하실 수 있을 것입니다.

 

 

예제

4 4 8      - 박스의 가로, 세로, 높이

 

3            - 사용할 큐브의 종류

 

0 10       - 1 x 1 x 1 큐브 10개 보유 

 

1 10       - 2 x 2 x 2 큐브 10개 보유

 

2 1         - 4 x 4 x 4 큐브 1개 보유

 

 

현재, 큐브의 최대 사이즈는 4 x 4 x 4이기때문에 박스를 4 x 4 x 4 부터 1 x 1 x 1까지 차례대로 분할해 봅시다.

 

박스는 4 x 4 x 8이기때문에 4 x 4 x 4로 분할하면 1 x 1 x 2 = 2개로 되는 것을 알 수 있습니다.

 

하지만, 4 x 4 x 4 큐브는 1개를 갖고 있기때문에 1개만 넣는 것이 가능합니다.

 

그리고 과거에 넣었던 큐브의 개수를 before라는 변수에 저장해 둡시다. 현재 before는 1인 상태입니다.

 

다음은, 박스를 2 x 2 x 2로 분할해 봅시다.

 

박스는 4 x 4 x 8이기 때문에 2 x 2 x 2로 분할하면 2 x 2 x 4 = 16개로 되는 것을 알 수 있습니다.

 

하지만, 4 x 4 x 4짜리 큐브가 이미 들어가 있는 상태이기때문에 4 x 4 x 4 큐브도 2 x 2 x 2 큐브로 분할함으로써 before에 8을 곱해주어야 합니다. 

 

따라서, 현재 박스에 들어갈 수 있는 2 x 2 x 2 큐브는 16 - 8 = 8개임을 알 수 있습니다. 그리고 이 8을 before에 더 해주게되면, before = 16이 됩니다.

 

마지막으로, 박스를 1 x 1 x 1로 분할해 봅시다.

 

박스는 4 x 4 x 8이기 때문에 1 x 1 x 1로 분할하면 4 x 4 x 8 = 128개로 되는 것을 알 수 있습니다.

 

하지만, 4 x 4 x 4와 2 x 2 x 2큐브가 이미 들어가 있는 상태이기때문에 기존에 before에다가 8을 곱해주어야합니다.

 

따라서, 현재 박스에 들어갈 수 있는 1 x 1 x 1큐브는 128 - 128 = 0개임을 알 수 있습니다.

 

1 x 1 x 1 분할이 완료되었으면, 더이상 분할 작업은 진행하지 않습니다.

 

이제, before과 실제 박스의 부피가 같은지 비교해 보아야 합니다.

 

before = 128이고, L X W X H = 128로 서로 같다는 것을 알 수 있습니다.

 

따라서, 박스에 들어갈 수 있는 큐브의 최솟값은 1 + 8 = 9개라는 결론을 내릴 수 있습니다.

 

아래는 위를 기반으로 작성한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int L = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());
 
        int N = Integer.parseInt(br.readLine());
 
        int[] cube = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int f = Integer.parseInt(st.nextToken());
 
            cube[t] = f;
        }
 
        long before = 0; // 이전에 사용된 큐브의 개수
        long ans = 0;
        for (int i = N - 1; i >= 0; i--) { // 반복문을 돌 때마다, 박스를 2^i x 2^i x 2^i로 분할해서 생각한다.
            // 현재 박스는 before보다 분할을 1번 더 시행했으므로 before의 개수를 2^3만큼 늘려주어야 한다.
            // 예를 들어, 4 x 4 x 4 분할 단계에서 before = 1이었다고 하자.
            // 그러면, 현재는 2 x 2 x 2 분할이 되므로 before = 8이 된다.
            before <<= 3;
 
            // 박스를 2^i x 2^i x 2^i만큼 분할해 주고, 전에 박스를 채웠던 큐브의 개수(before)만큼 빼 준다.
            // 만약, 분할이 불가능하다면 0이 나올 것이다.
            long possibleCube = (long) (L >> i) * (W >> i) * (H >> i) - before;
            long newCube = Math.min((long) cube[i], possibleCube); // 새롭게 박스에 추가된 큐브
 
            before += newCube; // 새롭게 추가된 큐브는 다음 반복문에서 과거가 되므로 before에 추가해 준다.
            ans += newCube;
        }
 
        if (before == (long) L * W * H) { // 위에서 계산한 before가 실제 박스의 부피와 같아야 함.
            bw.write(ans + "\n");
        } else { // 같지 않으면, 주어진 큐브로는 박스를 구성할 수 없다.
            bw.write("-1\n");
        }
 
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.