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

#1493 박스 채우기

난이도 : 골드 4

유형 : 그리디 / 분할정복

1493번: 박스 채우기

▸ 문제

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

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

▸ 입력

첫째 줄에 세 자연수 length width height가 주어진다.

둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다.

셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 i가 증가하는 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2i에서 i이다.

▸ 출력

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

 

문제 풀이  

그리디 목록에서 해당 문제에 접근했지만 그리디라기보다는 분할 정복, 구현에 더 가까운 문제였다. 풀다보니 재밌어서 여러 방식으로 풀어봤다.

 

풀이 코드 1 

먼저 접근한 방법은 현재 주어진 블록 중 가장 큰 조각부터 끼워넣는 방식이었다. 예로 4, 2, 1 이렇게 3가지 크기의 큐브가 주어졌다면 주어진 박스에 4를 먼저 넣어보고 그 다음 2를 넣어보고 그 다음 1을 넣어보는 것이다. 그렇게 모든 큐브를 넣어보고 박스가 다 채워졌으면 큐브의 수를 카운트하고, 박스가 다 채워지지 않았으면 -1을 출력하도록 했다.

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

public class Main {

	static int[] box, cube;
	static long fullV;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		box = new int[3];
		fullV = 1;
		for(int i=0; i<3; i++) {
			box[i] = Integer.parseInt(st.nextToken());
			fullV *= box[i];
		}
		int n = Integer.parseInt(br.readLine());
		
		cube = new int[n];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			cube[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
		}
		System.out.println(solve(n-1, 0, 0));
	}
	
	static long solve(int blockSize, long fill, long cnt) {
		long totalV = 1;
		for(int i=0; i<3; i++) {
			totalV *= box[i] >> blockSize;
		}
		
		int curCube = cube[blockSize];
		totalV -= fill;
		long fillCube = Math.min(curCube, totalV);
		if(blockSize == 0) {
			if((fill + fillCube) != fullV) {
				return -1;
			}
			return cnt+fillCube;
		}else {
			return solve(blockSize-1, fill+fillCube<<3, cnt+fillCube);	
		}
	}
}

 

풀이 코드 2

그런데 문제 유형에는 분할 정복이라는 키워드가 있었다. 위에서 내가 풀이한 방법은 분할 정복이 아니라 단순 재귀를 돌려준 반복처리였어서 분할 정복 방식으로도 풀이를 해봤다.

 

이는 오히려 약간 더 무식한 방법인데 l, w, h 중 가장 작은 변의 길이를 구해서 해당 크기에 맞는 사이즈를 끼워 넣는 방식이었다. 그리고 그렇게 넣은 블록을 제외하고 나오는 블록을 또 분기해서 처리하는 방식이다. 이 방식은 분기하는 조건이 더 세밀해서 시간이 훨씬 더 오래 걸린다. 그런데 만약 변의 길이가 2의 제곱꼴로 주어지지 않았다면 이렇게 구했어야 하는 게 맞는 것 같다.

 

위 그림처럼 한 변의 길이가 size인 정육면체를 제외한 부분을 3부분으로 나눠 분할정복하는 방식으로 풀이할 수 있다.

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

public class Main {

	static int[] box, cube;
	static int n;
	static boolean f = true;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		box = new int[3];
		for(int i=0; i<3; i++) {
			box[i] = Integer.parseInt(st.nextToken());
		}
        
		n = Integer.parseInt(br.readLine());
		cube = new int[n];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			cube[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
		}
		
		int res = divide(box[0], box[1], box[2]);
		if(f) {
			System.out.println(res);
		}else {
			System.out.println(-1);
		}
	}
	
	static int divide(int l, int w, int h) {
		if(l == 0 || w == 0 || h == 0 ) return 0;
		int k = Math.min(l, Math.min(w, h));
		
		int t = (int)(Math.log(k)/Math.log(2))+1;
		while(t--> 0) {
			if(n <= t || cube[t] <= 0)continue;
			cube[t]--;
			int size = (int)Math.pow(2, t);
			return divide(l-size, w, h) + divide(size, w-size, h) + divide(size, size, h-size)+1;
		}
		f = false;
		return -1;
	}
}

 

위에 결과 1번 풀이고 아래가 2번 풀이이다. 박스를 더 세심하기 나누어 분할 정복하는 방식이 훨씬 더 오래 걸리는 것을 확인할 수 있다. 만약 큐브의 크기가 2의 제곱꼴로 규칙적이지 않았다면 해당 방식이 맞겠지만 2의 제곱꼴로 주어졌기 때문에 간단하게 뱐복 재귀로 큐브를 끼워맞춰 풀이를 할 수 있다.