1493번 박스 채우기

문제 링크

박스 채우기

문제 풀이

입력으로 들어온 박스를 2^19 크기부터 2^0 크키의 정사각형 큐브로 채우는데 이때 최소한의 큐브를 사용해서 채운다. 각 큐브가 몇 개씩 사용되었는지 카운트를 하는데 이를 재귀호출로 구현하였다. 현재 박스를 들어갈 수 있는 최대 크기의 큐브로 채우고 남는 부분은 4개로 나눠 재귀호출한다. 그리고 나서 현재 가지고 있는 큐브의 갯수와 비교하여 채울 수 있는지 체크한다. 만약 한 단계 위 큐브의 갯수가 남았을 시 8을 곱해 현재 큐브의 필요한 갯수에 더해준다. 그리고 가지고 있는 큐브의 수와 필요한 큐브의 수 중 작은 값을 팔요한 큐브 수에서 빼준다.

구현

#include <iostream> 
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

ll length, width, height, N, ret;
vector<ll> cnt(21, 0), cube(21, 0);

void solve(ll index, ll l, ll w, ll h) {
    ll cubeSize[3] = { l, w, h };
    ll sqSize = 1 << index;
    sort(cubeSize, cubeSize + 3); // 가장 작은 길이 구하기

    if (cubeSize[0] == 0) return;	
    if (cubeSize[0] < sqSize) {
        solve(index-1, cubeSize[0], cubeSize[1], cubeSize[2]);
        return;
    }

    cnt[index] += (cubeSize[1] / sqSize) * (cubeSize[2] / sqSize);
    // 채우고 위에 남은 부분
    solve(index - 1, cubeSize[0] % sqSize, cubeSize[1], cubeSize[2]); 
    // 옆면에 남은 두 부분
    solve(index - 1, sqSize *  (cubeSize[0] / sqSize), 
        cubeSize[1] % sqSize, sqSize *  (cubeSize[2] / sqSize)); 
    solve(index - 1, sqSize *  (cubeSize[0] / sqSize), 
        sqSize *  (cubeSize[1] / sqSize), cubeSize[2] % sqSize);
    // 가장 작은 부분
    solve(index - 1, sqSize *  (cubeSize[0] / sqSize), 
        cubeSize[1] % sqSize, cubeSize[2] % sqSize);
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> length >> width >> height >> N;
    for (int i = 0; i < N; ++i) {
    	ll a, b;
    	cin >> a >> b;
    	cube[a] += b;
    }

    solve(19, length, width, height);

    for (int i = 19; i >= 0; --i) {
        cnt[i] += 8 * cnt[i + 1];
        ll s = min(cube[i], cnt[i]);
        cnt[i] -= s;
        ret += s;
    }
    if (cnt[0]) cout << -1;
    else cout << ret;
    return 0;
}