BOJ 1691 - 석판

BOJ 1691 - 석판

문제를 제대로 안읽었는데 대충 찍어서 맞췄다.

---

석판은 항상 남은 부분에서 가로나 세로로 쭉 잘라야 한다.

$dp[W][H]$를 $W, H$ 크기의 직사각형에서의 최소 손실이라고 정의한다.

현재 직사각형에서 가로나 세로로 쭈욱 자르며 반으로 나뉘어진 부분에 대해서 또 $dp$ 가 구해져있을 것이므로 점화식은 어렵지않다.

일단 현재 $W, H$에서 $N$개의 석판 중 둘 수 있는걸 아무거나 둬본다. $W$나 $H$에 딱 들어맞는다면 또 직사각형이 생길 것이고 아니라면 ㄱ 자 모양이 남을 것이다.

그런데 석판은 항상 남은 부분에서 가로나 세로로 쭉 잘라야 하므로 ㄱ자 모양은 무조건 두 가지 모양 중 하나로 나뉘어야 한다.

ㄱ자 모양이 꺾이는 부분의 정사각형이 어디에 속해있냐에 따라 다르다.

그러면 나뉠 수 있는 두 가지 경우 중 두 직사각형의 손실의 합중 최소를 구하면 된다.

void solve() {
   int Y, X, n;
   cin >> Y >> X >> n;
   vector<pi> a(n);
   for (auto &[h, w]: a) cin >> h >> w;
   auto dp = vec(Y + 1, X + 1, -1);
   // 최소 손실값
   function<int(int, int)> fn = [&](int h, int w) -> int {
      if (h <= 0 || w <= 0) return 0;
      int &ret = dp[h][w];
      if (~ret) return ret;
      ret = h * w;

      for (int i = 0; i < n; i++) {
         if (a[i].fi > h || a[i].se > w) continue;
         int extra_h = h - a[i].fi;
         int extra_w = w - a[i].se;

         int right_long = fn(h, extra_w);
         int right_short = fn(a[i].fi, extra_w);
         int bottom_long = fn(extra_h, w);
         int bottom_short = fn(extra_h, a[i].se);

         mina(ret, right_long + bottom_short);
         mina(ret, right_short + bottom_long);
      }

      return ret;
   };
   cout << fn(Y, X);
}