BOJ 1691 석판

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

1691번: 석판

 

dp로 풀 수 있는 문제입니다. 석판은 가로나 세로 방향으로 완전히 잘라야 한다는 점을 생각하면, 석판을 자르는 것을 부분문제로 나눠서 생각할 수 있습니다. 왼쪽 위를 원하는 모양의 석판 중 하나로 채워주면 두 가지 경우가 생깁니다. 가로로 먼저 자르고 세로로 자르는 것과 세로로 먼저 자르고 가로로 자르는 것입니다. 각 경우마다 새로 생기는 석판은 두 개가 되고 해당 석판을 다시 자르는 것으로 생각할 수 있습니다. 석판의 넓이가 0이라면 손실되는 면적은 0, 아무 석판도 끼워넣을 수 없다면 손실되는 면적은 $w \times h$입니다. 이렇게 재귀적으로 구한 두 경우의 답 중 최솟값이 해당 크기의 석판의 답이 됩니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define FF first
#define SS second
#define pii pair<int,int>

using namespace std;

int T, n, w, h, memo[606][606];
vector<pii> vec;

int dp(int w, int h) {
  if (memo[w][h] != -1) return memo[w][h];

  int ret = w * h;
  for (int i = 0; i < n; i++) {
    auto [ww, hh] = vec[i];
    if (ww > w || hh > h) continue;
    int tmp = min(dp(w - ww, h) + dp(ww, h - hh), dp(w, h - hh) + dp(w - ww, hh));
    ret = min(ret, tmp);
  }

  return memo[w][h] = ret;
}

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> w >> h >> n;

    vec.resize(n);
    for (int i = 0; i < n; i++) cin >> vec[i].FF >> vec[i].SS;

    memset(memo, -1, sizeof(memo));
    memo[0][0] = 0;

    cout << dp(w, h) << endl;
  }

  return 0;
}