백준 #1493 박스 채우기


BOJ #1493 - 박스 채우기

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

# 문제 분류

분할 정복, 수학

풀이 접근 방법


  1. 사실 분할 정복으로 못풀고 블로그 포스팅을 찾다가 방법을 발견했다.
  2. 면적만 주어진다면 될 것 같다는 생각이 들었긴 했는데, 232^3과 1, 1, 8짜리 직사각형이 주어진 경우 불가능하다는 것을 알 수 있다.
  3. 그래서 포스팅을 찾아보니,

    1. 일단 가장 큰 큐브부터 넣는 것은 자명하다.
    2. 그러나 그 면적을 직접적으로 비교하기엔 거의 불가능하다. 한 면이 적어도 10610^6이기 때문에..
    3. 따라서 오히려 직사각형을 그 승수만큼 낮춘다는 생각을 하고, 지금 내가 넣은 큐브를 계속해서 8배씩 곱한다.
    4. 8배씩 곱하는 이유는 면적은 세 면의 곱이고 각 면에 2씩 곱하면 232^3이기 때문...

분할 정복으로 직사각형 안의 점을 이용해 직사각형을 8등분해서 접근하는 코드도 보았지만,
이렇게 큐브를 낮춘다는 발상 자체는 유효한 것 같아 보였다.


#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
ll N, l, w, h;

vector<pl> p;

int main() {
    cin >> l >> w >> h >> N;
    for (int i = 0, a, b; i < N; i++) {
        cin >> a >> b;

        p.emplace_back(a, b);
    }

    sort(p.begin(), p.end());
    reverse(p.begin(), p.end());

    ll checker = 0, result = 0, tmp = 0;
    for (auto &v : p) {
        checker *= 1 << 3;
        ll tmp = min(v.second, (l >> v.first) * (w >> v.first) * (h >> v.first) - checker);
        checker += tmp;
        result += tmp;
    }

    cout << (l * w * h == checker ? result : -1);
}