[백준] 1493번 박스 채우기

1493번: 박스 채우기

탐욕법으로 가장 큰 큐브부터 박스에 넣어본 후

남은 부분들을 세 가지로 나누어 재귀로 계속 반복한다.

 

그림과 같이 현재 가장 큰 큐브 l, w, h를 제외하고 남은 1번, 2번, 3번 상자들은

각각 다시 하나의 상자로 생각하여 현재 가장 큰 큐브를 제외하고 남은 세 가지 상자들을

다시 각각 하나의 상자로 생각하고

...

이 과정을 가로, 세로, 높이 중 하나라도 0이 될 때까지 계속 반복한 후 빠져나와서 카운트를 출력한다.

 

가로, 세로, 높이 중 하나라도 0이 되기 전에 for문을 다 돌았을 때는

주어진 큐브들을 다 써도 박스를 채우지 못한 것이므로 fail을 체크해주고 -1을 출력한다.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int L, W, H, N, a, b, cnt = 0, fail = 0;
int cube[20];
vector <pair<int, int>> v; //2의 a승과 그 개수를 저장
void divide(int l, int w, int h, int idx) {
	if (l == 0 || w == 0 || h == 0) return;
	for (int i = idx; i < v.size(); i++) {
		if (v[i].second != 0 && l >= v[i].first && w >= v[i].first && h >= v[i].first) {
			v[i].second--;
			cnt++;
			divide(l - v[i].first, w, h, i);
			divide(v[i].first, w - v[i].first, h, i);
			divide(v[i].first, v[i].first, h - v[i].first, i);
			return;
		}
	}
	fail = 1;
}
int main() {
	cin >> L >> W >> H >> N;
	for (int n = 0; n < N; n++) {
		cin >> a >> b;
		cube[a] += b;
	}
	for (int i = 19; i >= 0; i--) {
		if (cube[i] != 0) {
			v.push_back(make_pair(pow(2, i), cube[i]));
		}
	}
	divide(L, W, H, 0);
	if (fail) cout << -1;
	else cout << cnt << endl;
	return 0;
}