백준 1493: 박스 채우기

#include <iostream>
#include <vector>
#include <utility> // pair
#include <algorithm>
#include <cmath> // pow
using namespace std;

int L, W, H, cnt;
bool flag = true;
vector< pair<int, int> > cubes; // (pow, cnt)

bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.first > b.first;
}

void solve(int l, int w, int h, int now) {
	if (l == 0 || w == 0 || h == 0) return;

	int i;
	int m = min(l, min(w, h));

	for (i = now; i < cubes.size(); i++) {
		if (cubes[i].second && m >= cubes[i].first) {
			int tmp = cubes[i].first; //현재 가장 큰 큐브의 변의 길이
			cubes[i].second--; // 사용할거니까 재고를 줄임
			cnt++; // 사용한 큐브의 개수 증가
			// 전체에서 사용한 큐브를 제외한 나머지 부분을 세 개로 나눠 동일한 작업 반복
			solve(l - tmp, w, h, i);
			solve(tmp, w - tmp, h, i);
			solve(tmp, tmp, h - tmp, i);
			return;
		}
	}
	flag = false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, ans, i, tmp1, tmp2;
	cin >> L >> W >> H;
	cin >> N;

	for (i = 0; i < N; i++) {
		cin >> tmp1 >> tmp2;
		cubes.push_back(make_pair(int(pow(2, tmp1)), tmp2));
	}

	sort(cubes.begin(), cubes.end(), cmp);
	solve(L, W, H, 0);

	if (flag) cout << cnt << endl;
	else cout << "-1" << endl;
	return 0;
}