[백준 1493] 박스 채우기

문제

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

 

알고리즘

분할정복, 그리디

 

풀이

박스를 큐브로 채워나갈 때, 필요로 하는 큐브의 갯수를 최소화 하는 문제입니다. 단 큐브의 사이즈는 2의 제곱형태로만 주어지는 제약이 있습니다. 

 

큐브길이가 2의 제곱형태로만 주어지는 점부터 살펴봅시다. 만약 이렇지 않았다면, 모든 큐브를 일일히 넣어보는 완전탐색을 해야합니다. 하지만 모든 길이가 배수와 약수 관계를 유지할 때, 무조건 큰 길이부터 넣는 그리디한 전략을 사용할 수 있습니다. 큰 길이의 큐브를 넣어야만 갯수를 최소화 할 수 있고, 예를들어 4x4x4큐브를 사용했다면 굳이 2x2x2큐브들로 그 자리를 대체할 이유가 없죠.

 

살펴보아야 할 점 중 또 한가지는 큐브길이는 제곱형태로 주어지지만 박스는 이와 관계없이 임의의 값이 주어집니다.

즉, 박스의 공간이 큐브의 크기보다 크다고 해서 무조건 계속 담아 나갈 수 있는 것은 아닙니다.

 

• 2 3 3 
  2
  0 10
  1 10

 

예를들어 문제의 입력이 위와같이 주어졌을 때, 박스의 크기는 2x3x3 = 18에 해당합니다. 2x2x2 큐브를 2개 담으려면 총 16공간만 있으면 담을 수 있다고 생각하기 쉽습니다. 하지만 2x2x2 큐브를 담을 수 없음을 금방 아실 수 있습니다.

 

즉 분할정복을 통해 각 큐브의 길이마다 몇개를 담을 수 있는지 파악한 후, 문제를 해결해 나가면 풀 수 있습니다.

 

++

저는 이 문제를 분할정복으로만 풀고, 다른분 코드를 참고하여 다시 복기하며 풀었습니다.

아래 첨부하는 코드는 위 설명과는 다른 제 코드이며, 위 풀이에 해당하는 코드가 궁금하신 분들은 이 문제를 맞추신 후

pichulia님 코드를 검색하셔서 보세요.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef pair<int, int> pii;
int L, W, H, N, ans;
pii cube[21];
bool check = true;
void recur(int l, int w, int h, int idx) {
    if (idx == -1) {
        if ((long long)l * w * h > 0) check = false;
        return;
    }
    auto& [len, cnt] = cube[idx];
    if (len > l || len > w || len > h || cnt == 0) {
        recur(l, w, h, idx - 1);
        return;
    }
    --cnt;++ans;
    recur(l - len, w, h, idx);
    recur(len, len, h - len, idx);
    recur(len, w - len, h, idx);

}

int main() {
    FAST;
    cin >> L >> W >> H >> N;
    rep(i, N) {
        int a, b;
        cin >> a >> b;
        cube[i].first = pow(2, a);
        cube[i].second = b;
    }

    recur(L, W, H, N - 1);

    if (!check) cout << -1;
    else cout << ans;

    return 0;
}