<문제 링크>
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.
입력
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;
}
}
}