백준 1493 - 박스 채우기

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

전략

박스 구석부터 채운다. 가능한 한 가장 큰 박스를 채우도록 한다. 가장 큰 박스를 놓지 않으면 다음과 같은 일이 벌어진다.

 

 

위 그림의 빨간 부분처럼 어중간하게 빈 영역이 발생하는데 이런 영역은 모서리에 있는 게 최적이고 그렇지 않으면 큰 큐브가 있어도 끼울 수 없는 경우가 있다.

 

따라서 이 문제는 큐브를 큰 거부터 채워가는 그리디 문제가 된다.

분할 정복

그러면 구석에서 배치할 수 있는 큰 큐브를 배치했다고 해보자. "다음으로 큰 큐브를 어떻게 배치하는가?"가 관심사가 되는데 배치 가능한 영역을 3~4개로 나누는 방법이 있다.

 

그림판으로 그려 가시성이 매우 좋지 않은 부분을 양해드린다.

 

위처럼 큐브를 채우지 않은 영역을 빨간색, 파란색, 초록색 영역으로 나눌 수 있고 재귀적으로 영역을 나눠가며 채울 수 있는지 확인하면 된다.

 

즉, 재귀 함수를 구성해서 분할 정복을 시행하는데 아직 아무것도 채우지 않은 상태인 (l, w, h)로 시작해서 채울 수 있는 가장 큰 큐브를 채운 뒤 영역만큼 분할하면 된다.

 

재귀 과정 중 인자로 주어진 l, w, h에서 하나라도 0이면 그것은 그 영역을 다 채웠다는 뜻이니 재귀를 종료하면 된다.

 

만약 큐브를 채우지 못했으면 그것은 아예 답을 만들 수 없으므로 즉시 재귀를 탈출하고 -1을 출력하도록 하면 된다.

 

어떻게 분할하는지는 구현을 참조하도록 한다. 참고로 소스코드에서는  l, w, h를 y, x, z로 표현했으니 참고에 유의한다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
int pref[21];
int ar[21];
bool nice = true;
int ans;
int x, y, z;
int n;
 
void solve()
{
  pref[0] = 1;
  for (int i = 1; i < 21; i++) pref[i] = pref[i - 1] * 2;
  cin >> x >> y >> z >> n;
 
  for (int i = 0; i < n; i++)
  {
    int a1, a2;
    cin >> a1 >> a2;
    ar[a1] = a2;
  }
 
  function<void(int, int, int)> recur = [&](int _x, int _z, int _y) {
    if (!_x or !_y or !_z) return;
 
    bool check = false;
 
    for (int i = 20; i >= 0; i--)
    {
      if (!ar[i]) continue;
 
      if (pref[i] <= _x and pref[i] <= _y and pref[i] <= _z)
      {
        ++ans;
        check = true;
        --ar[i];
 
        recur(pref[i], pref[i], _y - pref[i]);
        recur(_x - pref[i], _z, _y);
        recur(pref[i], _z - pref[i], _y);
        break;
      }
    }
 
    if (!check)
    {
      nice = false;
      return;
    }
  };
 
  recur(x, z, y);
 
  cout << (nice ? ans : -1);
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록