[백준] 1493 - 박스 채우기

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

1493번: 박스 채우기

 

채워야 하는 박스는 직육면체이고, 채우는 큐브는 정육면체 형태이다.

그래서 항상 큰 것부터 넣는 것이 그리디한 방법이라고 할 수 있겠다.

 

그래서 큰 것을 넣으면 어떻게 되는가?

만약 L * W * H 크기(L <= W <= H)의 박스에 a * a * a 크기의 큐브를 넣는다면,

 

(L - a) * W * H,

a * W * (H - a),

a * (W - a) * a

 

총 3개의 직육면체가 나오게 될것이다.

그래서 가장 큰 큐브부터 하나씩 써가며 칸을 채워나가면 된다.

 

#include <iostream>
#include <climits>
using namespace std;

int min(int a, int b, int c) {
	if (a <= b && a <= c) return a;
	if (b <= a && b <= c) return b;
	return c;
}

int n, a[21];

int go(int w, int m, int h) {
	
	if (w == 0 || m == 0 || h == 0)return 0;

	int idx = -1;

	for (int i = n - 1; i >= 0; i--) {
		if (a[i] && (1 << i) <= min(w, m, h)) {
			idx = i;
			break;
		}
	}

	if (idx == -1) {
		cout << -1;
		exit(0);
	}

	int c = 1 << idx;
	a[idx]--;
	int ret = go(w - c, m, h) + go(c, m, h - c) + go(c, m - c, c) + 1;
	return ret;
}

int main() {
	int l, m, h;
	cin >> l >> m >> h >> n;

	for (int i = 0; i < n; i++) {
		int c, b; cin >> c >> b;
		a[c] = b;
	}

	cout << go(l, m, h);
}