[백준 1493번] 박스 채우기(Java)

 

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

1493번: 박스 채우기

이 문제는 골드 3 문제로, 그리디 알고리즘, 분할정복을 이용해서 푸는 문제입니다. 그리디 알고리즘보다 분할정복 성격이 강하기에 분할정복 카테고리로 넣었습니다.

---

그리디 알고리즘? 

그리디 알고리즘은 탐욕 알고리즘이라고도 불리는데 매 순간 최선의 선택을 하는 알고리즘이라고 생각하면 됩니다. 매 순간 최적을 선택한다는 장점은 있지만, 종합적으로 보면 제일 최선은 아닐 수 도 있습니다. 

---

풀이

문제를 보면, 길이,너비, 높이 값이 주어진 박스가 존재할때, 현재 가지고 있는  큐브를 이용해서, 채우는 문제입니다. 

단 박스를 채울 수 있는 최소의 경우를 구해야합니다.  그럼 어떡해야 박스를 채울 수 있는 큐브의 최소 개수를 구할 수 있을까요?

 

해결책1. 크기가 큰 큐브부터 차례대로 넣어준다!

 크기가 큰 큐브부터 차례대로 채워주면, 매 순간 마다 채울 수 있는 부피가 크기 때문에 최소 개수를 구할 수 있을 것입니다. 이를 위해 필요한 것이 초반에 간략하게 설명한 그리디 알고리즘입니다. 

그리디 알고리즘은 매번 최적의 수를 선택하기 때문입니다. 그렇다면 매 순간  넣을 수 있는  가장 큰 큐브를 넣어 주면 되는 것이죠.

하지만, 이런 방식을 쓰면 박스의 남은 공간에 대해 큐브를 어떻게 채울지에 대한 고민이 남습니다. 물론 해결책이 있죠

 

해결책2. 남은 부분을 3부분으로  나눠준다!

바로  남은 부분을 3개의 박스로 나눠주는 것입니다! 이해를 돕기 위해 사진을 가지고 왔습니다

6x6x5 박스

제가 그림을 잘 그리지 못해 알지오매스(https://www.algeomath.kr/main.do)  라는 사이트를 이용해  6x6x5 인 박스를 구현해봤습니다.  이때 제가 갖고 있는 큐브 중 가장 큰 큐브인 4x4x4 큐브를 이 박스에 채워 본다고 가정합시다

4x4x4큐브

그럼 박스는 이런 모양을 띄게 됩니다. 이제 제일 큰 큐브를 채웠으니, 남은 부분에 대해서도 큐브를 채워넣어야겠죠. 

그럼 박스의 남은 부분은 어떻게 3 부분으로 나눌 수 있을까요?

앞 모습

뒤

이런식으로 색깔을 구분해서 3개의 박스를 만들었습니다.  이 3개 박스의 각각 길이, 너비, 높이를 구하면 다음과 같습니다.

노란 박스: 6x6x1

파란 박스: 6x2x4

초록 박스: 2x4x4 

이를 식으로 표현하면 다음과 같습니다. 

박스의 길이가 L, 너비가 W, 높이가 H이고 N*N*N 큐브를 넣었다고 가정했을때
Box1=L * W * (H-N)
Box2=L* (W-N) * N
Box3= (L-N)* N * N
이 3개의 박스를 각각 재귀 호출을 이용해 해당 박스에는 큐브가 최소 몇개 들어가는지 구하면 됩니다.

---

코드

import java.util.*;
import java.io.*;
public class Main {
	static int [] cube=new int[20]; //큐브의 개수
	static int count=0; // 박스안에 들어갈 큐브를 카운트하는 변수
	static boolean state=true;//박스안에 큐브가 들어가는지 판단하는 bool 변수
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int length=Integer.parseInt(st.nextToken());
        int width=Integer.parseInt(st.nextToken());
        int height=Integer.parseInt(st.nextToken());
        int n=Integer.parseInt(br.readLine());
        
        for(int i=0;i<n;i++ ) {
        	st=new StringTokenizer(br.readLine());
        	int idx=Integer.parseInt(st.nextToken());
        	cube[idx]=Integer.parseInt(st.nextToken());

        }
        //메소드 호출
        GetCube(length,width,height);
        //만약 큐브를 다 채웠으면 count 출력 아니라면 -1 출력
        if(state==true)
        	bw.write(String.valueOf(count));
        else
        	System.out.println(-1);
        bw.flush();
        bw.close();
        
		}
	
	
	public static void GetCube(int l,int w,int h) {
    //만약 하나라도 0이면 없다는 뜻이므로 리턴
		if (l==0||w==0||h==0) {
			return;
		}
		int cubeSide=0;
		//큐브 큰것 부터 찾음 
		for(int i=19;i>=0;i--) {
			
			state=false;
			cubeSide=1<<i;//2^i
            //해당 큐브의 변이 채워야하는 상자의 길이보다 작으며, 개수가 0보다 많아야한다
			if(cubeSide<=l&&cubeSide<=w&&cubeSide<=h&&cube[i]>0) {
				//만약 넣었으면 해당 큐브 개수 1감소, count 1 증가, state = true
				cube[i]--;
				count++;
				state=true;
		
				break;
			}
		}
		//state가 false이면 박스안에 넣을 큐브가 더이상 없다는 것이므로 리턴 
		if(!state) 
			return ;
		
		//박스를 자르면 남는 세개의 박스에 대해 호춣한다.
		
		GetCube(l-cubeSide,cubeSide,cubeSide);
		GetCube(l,w-cubeSide,cubeSide);
		GetCube(l,w,h-cubeSide);
		
	}

}