1691번: 석판

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


$O(n+wh(w+h))$

dp[i][j]: i*j를 만들 때 최소 손실
dp[i][j]=
if (i*j가 주어진 대리석 석판 중에 있다면)
손실이 없다.
-> 0
else
가로 혹은 세로로 잘라 두 개의 직사각형으로 만든뒤 이미 구한 dp값 참조한다.
->min(min(dp[k][j]+dp[i-k][j]), min(dp[i][k]+dp[i][j-k]), i*j)

#include<cstdio>
#include<algorithm>
using namespace std;
int w, h, n, dp[601][601];
int main() {
    scanf("%d%d%d", &w, &h, &n);
    for (int i = 1; i <= w; i++) for (int j = 1; j <= h; j++) dp[i][j] = i*j;
    for (int i = 0, x, y; i < n; i++) scanf("%d%d", &x, &y), dp[x][y] = 0;
    for (int i = 1; i <= w; i++) {
        for (int j = 1; j <= h; j++) {
            for (int k = 1; k < i; k++) dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k][j]);
            for (int k = 1; k < j; k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j - k]);
        }
    }
    printf("%d", dp[w][h]);
    return 0;
}