[BOJ]백준 1493번: 박스 채우기/DivideAndConquer

www.acmicpc.net/problem/1493

1493번: 박스 채우기

분할 정복을 이용한 문제

L * W * H의 길이를 가진 박스를 분할해서, 가지고 있는 큐브들로 채우는 문제이다

큐브의 한 변은 2의 거듭제곱 꼴로 제한되어 있다

 

이 때, 박스에 같은 부피의 빈 칸이 있다면 무조건 큰 큐브로 채우는게 유리하다

Why? 만약 K*K*K 크기의 빈 칸을 현재 사용 가능한 작은 큐브로 채우는게 큰 큐브보다 총 큐브 수가 적다고 가정.

but 작은 큐브는 큰 큐브보다 무조건 3개 이상(부피가 1/4배이기 때문) 사용해야 한다.

그래서 현재 사용하고 남은 부피에서 대소 관계를 다시 복구해야 하는데, 이것은 성립하지 않는다

 

따라서 큰 큐브부터 채우는 greedy한 방식을 사용한다.

 

분할 정복은 현재 문제를 input size가 작은 subproblem으로 쪼개는 게 핵심 ❗❗이기 때문에

length, width, height의 parameter를 가진 재귀 함수로 구현해준다.

 

현재 채울 수 있는 가장 큰 크기의 큐브를 채우고 나면, 박스는 세 덩어리로 나누어 진다(아래의 그림과 같음)

 

따라서 세 경우에 대해 재귀호출을 해주고, 하나의 큐브를 사용했으므로 사용한 큐브 수에 +1

만약 셋 중 한 값이라도 0이면, 해당 box의 부피는 0이므로 0을 리턴해준다

 

#include <cstdio>
#include <math.h>
int L, W, H,n,cube[21];
bool f = 1;
int func(int l, int w, int h) {
	if (!l || !w || !h)return 0;
	int k = l;
	if (w < k)k = w;
	if (h < k)k = h;

	int t = log2(k);
	do {
		if (!cube[t])continue;
		cube[t]--;
		int T = pow(2, t);
		return func(l - T, T, h) + func(l, w - T, h) + func(T, T, h - T)+1;
	} while (--t >= 0);
	f = 0;
	return -1;
}
int main() {
	scanf("%d%d%d%d", &L, &W, &H,&n);
	for (int i = 0,a,b; i < n; i++) {
		scanf("%d%d", &a, &b);
		cube[a] = b;
	}
	int ans = func(L, W, H);
	if (f)
		printf("%d", ans);
	else printf("-1");
	return 0;
}

Time Complexity는 input으로 들어오는 cube 수에 따라 다르다