본문 바로가기
Algospot

CAKECUT

by Haeine 2017. 8. 22.

<문제 링크>

https://algospot.com/judge/problem/read/BOOKTHIEF

문제

You are given a rectangular cake of integral dimensions w × h. Your goal is to divide this cake into m rectangular pieces of integral dimensions such that the area of the largest piece is minimal. Each cut must be a straight line parallel to one of the sides of the original cake and must divide a piece of cake into two new pieces of positive area. Note that since a cut divides only a single piece, exactly m−1 cuts are needed.

If w = 4, h = 4, and m = 4, then the following cuts minimize the area of the largest piece would be shaped as the first example. However, if w = 4, h = 4, and m = 3, then the second picture would be the optimal.

judge-attachments/26cf22fe33f9bea02c0438cceaef86af/stf2004A.png

 

입력

The input test file will contain multiple test cases, each of which consists of three integers w, h, m separated by a single space, with 1 <= w, h, m <= 20 and m <= wh. The end-of-file is marked by a test case with w = h = m = 0 and should not be processed.

 

출력

For each test case, write a single line with a positive integer indicating the area of the largest piece.

 

위 문제는 최적화 문제로 볼 수 있다. 자를 수 있는 경우의 수 중에서 가장 넓은 몉적이 최소가 되는 경우를 찾으면 된다. 경우의 수를 구하는 문제와 마찬가지로 이처럼 최선의 경우를 구하는 문제 또한 동적계획법으로 풀이가 가능하다.

 

점화식은 아래와 같이 세울수 있다.

dp[i][j][k] = min(dp[i][j][k], max(dp[i - t][j][k - a], dp[t][j][a])   1 <= t < i, 1 <= a < k

               min(dp[i][j][k], max(dp[i][j - t][k - a], dp[i][t][a])   1 <= t < j, 1 <= a < k

 

위와 같은 점화식으로 문제를 해결하는 코드는 아래와 같다.

 

 

const int INF = 987654321;
int w, h, m;

int main() {
 while (true) {
  cin >> w >> h >> m;
  if (w == 0 && h == 0 && m == 0)
   break;
  int dp[21][21][21];
  memset(dp, 0, sizeof(dp));
  if ((w * h) % m == 0)
   cout << (w * h) / m << endl;
  else {
   for(int i = 1; i <= w; ++i)
    for (int j = 1; j <= h; ++j)
     for (int k = 1; k <= min(i * j, m); ++k) {
      if ((i * j) % k == 0)
       dp[i][j][k] = (i * j) / k;
      else{
       dp[i][j][k] = INF;
       for (int t = 1; t < i; ++t)
        for(int a = 1; a < k; ++a)
         dp[i][j][k] = min(dp[i][j][k], max(dp[i - t][j][k - a], dp[t][j][a]));
       for (int t = 1; t < j; ++t)
        for(int a = 1; a < k; ++a)
        dp[i][j][k] = min(dp[i][j][k], max(dp[i][j - t][k - a], dp[i][t][a]));
      }
     }
   cout << dp[w][h][m] << endl;
  }
 }
}

 

 

'Algospot' 카테고리의 다른 글

DICT  (0) 2017.10.14
CHANGE  (0) 2017.08.28
FENCE  (0) 2017.08.18
MATEXP  (0) 2017.08.17
QUADTREE  (0) 2017.08.16

관련글

티스토리툴바