[백준] 1493번: 박스 채우기 - java

 

나의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringBuilder sb;
	static StringTokenizer st;
	static int L, W, H, N, min_cnt;
	static int[] cube;
	static boolean check;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		L = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(br.readLine());
		cube = new int[20];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken()); // 큐브 종류
			int cnt = Integer.parseInt(st.nextToken()); // 큐브 갯수
			cube[num] = cnt;
		}
		divide(L, W, H);
		if (check)	System.out.println(min_cnt);
		else 	System.out.println(-1);
	}
	
	static void divide(int l, int w, int h) {
		if (l==0 || w ==0 || h==0 )	return;
		check = false;
		int size = 0;
		for(int i=19; i>=0; i--) {
			if (cube[i] == 0)	continue;
			
			size = 1<<i;
			if (l >=size && w >= size && h >= size) {
				cube[i]--;
				min_cnt++;
				check = true;
				break;
			}
		}
		if (!check)return; 	// 큐브를 채울 수 없는 경우
		divide(l-size, size, size);
		divide(l,w-size, size);
		divide(l, w, h-size);
		
	}
}

 

분할정복을 이용해서 풀었다.

큐브 크기가 큰 것부터 내림차순으로 탐색해보며, 큐브가 존재하고, 큐브 사이즈가 L,W,H 이하라면,

해당 큐브를 사용한다.

=> cube[i]--; / min_cnt++; 

이때 큐브를 사용한 것이므로, check = true 로 설정한다.

 

위 그림처럼 노랑색 큐브를 넣고 난 이후 남은 구역을 크게 3구역으로 분할하여 탐색하였다.

즉, 파랑색 부분은 가로가 w-i, 세로가 i, 길이는 l이다.

빨강색 부분은 가로가 i, 세로가 i, 길이는 l-i 이다.

흰색 부분은 가로가 w, 세로가 h-i, 길이는 l 이다.

 

만약, check 가 false라면, 큐브로 채울 수 없는 경우이므로 return 한다.

 

 

divide 함수의 기저 조건은 다음과 같다. 즉, 남아있는 길이가 0이라면 return 해준다.