1493번: 박스 채우기

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


$O(n+{\lg l}^4)$

직육면체를 최대한 큰 큐브를 먼저 사용해 구성해야 함은 자명하다.
문제는 몇 개의 큐브를 사용한 후에 남은 직육면체를 어떻게 고려할 것인지일 것이다.
주어진 직육면체를 모든 종류의 큐브가 무수히 많다고 가정하고 최대한 적은 수로 쪼개보자.
이 과정은 분할정복으로 간단히 구현된다. 자세한건 소스를 참고하자.
이렇게 쪼개보면 종류별로 큐브 수가 나오는데 여기서 큰 큐브는 쪼개서 작은 큐브가 될 수 있다.
이를 고려해서 주어진 큐브로 직육면체를 구성하는 방법을 따지면 된다.

#include<stdio.h>
typedef long long ll;
int l, w, h, n, a[20], r;
ll b[21];
void f(int x, int y, int z) {
    if (!x || !y || !z) return;
    for (int i = 19, t; i >= 0; i--) {
        t = 1 << i;
        if (x / t && y / t && z / t) {
            b[i] += (ll)(x / t)*(y / t)*(z / t);
            for (int j = 1; j < 8; j++) f(j & 1 ? x%t : x / t*t, j & 2 ? y%t : y / t*t, j & 4 ? z%t : z / t*t);
            break;
        }
    }
}
int main() {
    scanf("%d %d %d %d", &l, &w, &h, &n);
    for (int i = 0, x, y; i < n; i++) scanf("%d %d", &x, &y), a[x] = y;
    f(l, w, h);
    for (int i = 19; i >= 0; i--) {
        b[i] += b[i + 1] * 8;
        ll t = a[i] > b[i] ? b[i] : a[i];
        b[i] -= t;
        r += t;
    }
    printf("%d", b[0] ? -1 : r);
    return 0;
}