백준 1493번 : 박스 채우기 - 그리디 , 분할정복 C++

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

1493번: 박스 채우기

1.문제설명

 

큰 정육면체부터 채워보면서

 

다 채울 수 있는지 재귀적으로 구해볼 수 있다.

 

남은 부분을 새로운 박스로 만드는 것에 대해 

 

깊이 생각해볼 필요가 있다.

 

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int arr[20] , ans;
bool flag;


void rec(int l, int w, int h) {

	if (l == 0 || w == 0 || h == 0) return;

	for (int i = 19; i >= 0; i--) {
		if (arr[i] == 0) continue;

		int cur = 1 << i;

		if (l >= cur && w >= cur && h >= cur) {
			arr[i]--;

			rec(l, w, h - cur);
			rec(l-cur, w, cur);
			rec(cur, w - cur, cur);


			ans++;

			return;
		}
	}

	flag = true;

	return;
}



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

	int l, w, h, n;
	cin >> l >> w >> h;
	cin >> n;

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

	rec(l, w, h);

	if (flag) {
		cout << -1 << '\n';
	}
	else {
		cout << ans << '\n';
	}
	

	return 0;
}