백준 1493 / C++

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

1493번: 박스 채우기

 

[ 풀이 ]

큐브들은 모두 작은걸로 큰걸 채울 수 있다. 따라서 그리디하게 길이에 맞는 가장 큰 큐브부터 사용하면 된다.

(각 큐브가 작은것으로 큰걸 채우지 못하면 그리디를 사용할 수 없다.)

큐브를 사용했다면 박스는 세 부분으로 나뉜다. 이제 이 세부분으로 divide&conquer 해주면 된다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
int a, b, c, u, v, n, cube[22], ans = 0;

// 길이 x, y, z인 박스 나누기
void go(int x, int y, int z) {
	if (!x || !y || !z) return;
	int k = min({ x, y, z });
	int idx = (int)log2(k);
	int flag = 0;
	// 길이에 맞는 제일 큰 큐브 선택 
	for (int i = idx; i >= 0; i--) {
		if (cube[i]) {
			flag = 1;
			idx = i;
			break;
		}
	}
	//없다면 채울 수 없다.
	if (!flag) {
		cout << -1;
		exit(0);
	}
	// 채웠다면 
	ans++, cube[idx]--;
	int len = 1 << idx;
	go(x - len, y, z);
	go(len, y, z - len);
	go(len, y - len, len);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> a >> b >> c >> n;
	for (int i = 0; i < n; i++) {
		cin >> u >> v;
		cube[u] = v;
	}
	go(a, b, c);
	cout << ans;
}