03.11. 박스 채우기[Greedy Algorithm][백준 1493]

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

1493번: 박스 채우기

 

Algorithm classification : Greedy Algorithm, Math, Divide and conquer

 

03.11.1. Problem

Sejun has a box with dimensions length × width × height. And Sejun tries to fill this box with cubes. A cube has the shape of a cube, and the length of one side is the power of two. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...)

 

Given the type and number of cubes and the type of box Sejun has, write a program that prints the minimum number of cubes required to fill the box.

 

03.11.2. Input limit

The first line gives three natural numbers length, width and height. In the second line, the number N of cube types that Sejun has is given.

 

The cube type A_i and the number B_i are given in the order of increasing i in total N rows from the third row.

 

The type of cube is 2^i to i, which is used to indicate the length of one side.

 

03.11.3. Output

The first line prints the minimum number of cubes required. If it cannot be filled, -1 is output.

 

03.11.4. Solution

조금 생각해볼 거리를 제공하는 문제입니다. 직육면체를 직접 그리셔서 어떻게 해야할지 특히 남은 공간을 어떻게 채울지 고민하셔야 합니다. 일단 제대로 작동하는 code를 보기전에 제대로 작동하지 않는 code를 보시면 이해가 되실겁니다. 아래 code가 어떤 메커니즘을 채택하였는지 고민하시면 됩니다.

void cal(int l, int w, int h, int i){
	if(l <= 0 || w <= 0 || h <= 0) return;
	if(i < 0) return;
	
	int temp = (l / k) * (w / k) * (h / k);
	
	
	if(k <= l && k <= w && k <= h){
		while(datac[i]){
			c++;
			datac[i]--;
			v -= pow(pow(2, i), 3);
		}
	}
	printf("%d\n", c);
	cal(l % k, w, h, i-1);
	cal(l / k * k, w % k, h, i-1);
	cal(l / k * k, w / k * k, h % k, i-1);
}

 

main함수는 아래와 같습니다.

int main()
{
	scanf("%ld %ld %ld", &l, &w, &h);
	scanf("%ld", &n);
	for(i = 0; i < n; i++){
		scanf("%ld %ld", &a, &b);
		datac[a] = b;
	}
	for(i = 0; i < 20; i++){
		datap[i] = pow(2, i);
	}
	v = l * w * h;
	cal(l, w, h, 19);

	printf("%ld", v ? -1 : c);
	return 0;
}

 

위의 cal function code를 잘 분석해보셨나요? 그렇다면 제대로 동작하는 아래의 code도 보시죠.

void cal(int l, int w, int h, int i){
	if(l <= 0 || w <= 0 || h <= 0) return;
	if(i < 0) return;
	
	int k = datap[i];
	if(datac[i] && k <= l && k <= w && k <= h){
		c++;
		datac[i]--;
		v -= pow(pow(2, i), 3);
		cal(l - k, w, h, i);
		cal(k, w - k, h, i);
		cal(k, k, h - k, i);
		return;
	}
	cal(l, w, h, i-1);
}

 

 

여러분께 도움을 드리고자 Test case를 아래에 적어두겠습니다.

2 3 3
2
0 10
1 10
> 11


4 4 4
2
0 8
1 7
> 15