#1493 박스 채우기

박스 채우기는 일견 어려워 보이지만, 채워야할 큐브들의 2의 멱승길이를 가지는 정육면체라는 것에 착안하면 어렵지 않게 풀릴 수 있습니다.

 

예를 들어서 길이 2인 공간은 길이 1인 정육면체 큐브 8개로 채울 수 있죠.

 

저는 이 문제를 풀 때, 가장 큰 큐브부터 시작해서 작은 큐브로 채우는 것을 생각했습니다.  

채울 수 있는 박스들의 최대 크기는 \(2^{19}\)이므로 이 크기의 큐브가 몇개 필요한지 우선 계산을 합니다.

이게 0개이면 다음 크기로 가겠죠.  일단 큰 큐브로 채우고 나면, 남아있는 부분들이 자잘하게 생기는데, 이 부분들이 총 7 부분이라고 생각을 했습니다.   그리고 같은 함수로 큐브 크기를 한단계 낮추어서 채우도록 합니다.

그리고 필요한 큐브의 갯수를 v[] 배열에 담아두고, 주어진 큐브의 배열 s[]와 비교해서, 필요한 갯수를 충분하게 할 수 있으면 모두 그 큐브로 채우고 다음 단계로 내려가는 것이죠.  하지만 주어진 큐브의 개수가 부족하면, 부족한 개수만큼 그 다음단계로 넘어가는데 이때 8을 곱하게 됩니다.

 

박스 채우기

 

이 작업들을 계속하게 되면, 결국 원하는 결과를 얻게 됩니다.

 

예를 들어서 10x12x22 의 박스가 있습니다.  크기 1 큐브가 100개, 크기 2인 큐브가 230개, 크기 4인 큐브가 5개 있다면,

박스 공간 나누기를 먼저 합니다.

 

크기 8인 큐브 : 2

그러면 7개의 공간은 2x8x8, 8x4x8, 8x8x6, 2x4x8, 2x8x6, 8x4x6, 2x4x6이 됩니다.

크기 4인 큐브 : 0, 4, 4, 0, 0, 2, 0 = 10

크기 2인 큐브 : 32, 0, 16, 8, 8, 8, 6 = 78

형태가 됩니다.  사실 위 수치는 틀릴 수도 있습니다.  대충 암산으로 계산해서요.

크기 8인 큐브가 없으니, 크기 4인 큐브가 16개 더 필요해서 총 26개가 필요한데, 5개가 있으니, 21개가 여전히 부족합니다.

크기 2인 큐브는 168 + 78 = 246개가 필요합니다.  크기 2인 큐브가 230개 있으니, 이를 제하면 모자란 것은 16개입니다.

필요한 크기 1인 큐브는 128개입니다.  하지만 100개밖에 없으니 결국 이 박스는 채울 수 없습니다.

 

제가 작성한 코드입니다.  코드는 참고용으로 봐주세요.

//----------------------------------------------------------
//    baekjoon #1493 - Filling box
//        - by Aubrey Choi
//        - created at 2020-01-01
//----------------------------------------------------------
#include <stdio.h>

long long v[20], s[20];
long long MIN(long long a, long long b) { return a<b?a:b; }
void fill(int w, int h, int d, int k)
{
    if(k<0) return;
    int wn=w>>k, hn=h>>k, dn=d>>k, wm=w&((1<<k)-1), hm=h&((1<<k)-1), dm=d&((1<<k)-1);
    if(!wn||!hn||!dn) { fill(w, h, d, k-1); return; }
    v[k]+=(long long)wn*hn*dn;
    fill(wm, hn<<k, dn<<k, k-1);
    fill(wn<<k, hm, dn<<k, k-1);
    fill(wn<<k, hn<<k, dm, k-1);
    fill(wm, hm, dn<<k, k-1);
    fill(wm, hn<<k, dm, k-1);
    fill(wn<<k, hm, dm, k-1);
    fill(wm, hm, dm, k-1);
}
int main()
{
    int w, h, d, m, i, k;
    scanf("%d%d%d%d",&w,&h,&d,&m);
    fill(w,h,d,19);
    while(m--) { scanf("%d%d",&i,&k); s[i]=k; }
    for(i=19,w=0;i>=0;i--)
    {
        m=MIN(v[i],s[i]);
        v[i]-=m, s[i]-=m; w+=m;
        if(v[i]&&i>0) v[i-1]+=v[i]<<3;
    }
    printf("%d\n", v[0]?-1:w);
}