[BOJ 1493 // C++] 박스 채우기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1493번 문제인 박스 채우기이다.
문제는 아래 링크를 확인하자.

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

1493번: 박스 채우기

모든 박스의 변의 길이가 2의 거듭제곱 꼴이므로, 글쓴이는 큰 박스부터 최대한 이용하는 방향의 greedy한 전략을 이용하여 문제를 해결하였다.

 

큰 박스서부터 사용할 수 있는 만큼 최대한 사용하는 greedy 알고리즘을 이용하면 문제를 해결할 수 있다.

 

박스의 세 변의 길이를 \(L\), \(W\), \(H\)라 하자. 주어진 박스를 완전히 채우기 위해 한 변의 길이가 1인 큐브가 최소 몇 개 필요할까? 나머지 모든 큐브의 한 변의 길이는 2의 배수이므로, 한 변의 길이가 1인 큐브 없이 채워지는 박스의 최대 부피는 \(LWH - L'W'H'\)와 같다는 것을 관찰할 수 있다. 여기에서 \(L'\), \(W'\), \(H'\)은 각각 \(L\), \(W\), \(H\)보다 작거나 같은 가장 큰 2의 배수이다.

 

만약 한 변의 길이가 1인 큐브가 \(LWH - L'W'H'\)개보다 적다면 박스를 주어진 큐브로 채울 수 없음을 알 수 있다. 한 변의 길이가 1인 큐브가 \(LWH - L'W'H'\)개 이상인 경우 해당 큐브를 이용해 박스의 채워지지 않은 부분이 세 변의 길이가 \(L'\), \(W'\), \(H'\)와 같은 모양이 되게끔 채울 수 있다.

 

남은 박스와 큐브의 각 변의 길이를 반으로 나누면 다시 위의 상황으로 돌아가게 되며, 이를 반복해 박스를 완전히 채울 수 있다면 이것이 최소 개수의 큐브를 이용해 박스를 채운 것임은 자명하다. 위 과정을 따라가면 작은 크기의 큐브부터 차례대로 필수로 사용해야 하는 개수씩만을 사용하고 전체 박스를 채우게 되기 때문이다.

 

한편, 위 과정을 반복하면서 한 변의 길이가 2인 큐브부터는 해당 단계의 큐브가 \(LWH - L'W'H'\)개보다 적더라도 박스를 채우는 것이 바로 불가능해지는 것은 아님을 관찰하자. 이 단계까지 오기 전 단계들에 사용된 큐브들을 합쳐 남은 부분을 채울 수 있는 경우가 존재하기 때문이다. 다만 이와 같이 박스를 채우는 것은 사용하는 큐브의 개수를 최소화해야 하는 이 문제의 특성상 이 단계의 큐브가 부족한 경우에만 사용하는 것이 항상 이득임을 확인하자.

 

이제 위 과정을 거꾸로 생각하면, 이는 주어진 직육면체를 사용할 수 있는 큰 것부터 사용하기 시작해 최대한 채우려고 시도하는 것과 같은 과정임을 알 수 있다. 이를 구현해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll arr[20];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	ll A, B, C; cin >> A >> B >> C;
	int N; cin >> N;
	while (N--) {
		ll a, b; cin >> a >> b;
		arr[a] = b;
	}

	ll ans = 0;
	ll counted = 0;
	ll idx = 1 << 20;
	for (int i = 19; i >= 0; i--) {
		idx >>= 1;
		counted <<= 3;
		ll x = A / idx, y = B / idx, z = C / idx;
		ll cnt = x * y * z - counted;
		ll box = min(cnt, arr[i]);
		ans += box;
		counted += box;
	}
	if (counted == A * B * C) cout << ans;
	else cout << -1;
}