백준 5463 / C++

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

5463번: 건포도

 

[ 풀이 ]

나눴을 때 합을 계산해주려면 시작점 좌표와 끝점 좌표를 알아야 한다. 

마침 n,m도 50이하다. dp[sx][sy][ex][ey]를 (sx,sy)~(ex,ey)로 만들어지는 직사각형에서 건포도의 최소 양이라고 하자.

전이는 2가지다. 가로로 자르는 경우, 세로로 자르는 경우. 이후 식을 세우는건 쉬우므로 코드로 대체한다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
int n, m, psum[51][51], dp[51][51][51][51];

// (sx,sy)~(ex,ey) 누적합 
int sum(int sx, int sy, int ex, int ey) {
	return psum[ex][ey] - psum[ex][sy - 1] - psum[sx - 1][ey] + psum[sx - 1][sy - 1];
}

int go(int sx, int sy, int ex, int ey) {
	if (sx == ex && sy == ey) return 0;
	int& ret = dp[sx][sy][ex][ey];
	if (~ret)return ret;
	ret = 1e9;
	// 세로로 자름 
	for (int k = sy; k < ey; k++) {
		ret = min(ret, go(sx, sy, ex, k) + go(sx, k + 1, ex, ey) + sum(sx, sy, ex, ey));
	}
	// 가로로 자름 
	for (int s = sx; s < ex; s++) {
		ret = min(ret, go(sx, sy, s, ey) + go(s + 1, sy, ex, ey) + sum(sx, sy, ex, ey));
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> psum[i][j];
			// 누적합 전처리 
			psum[i][j] += psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1];
		}
	}
	cout << go(1, 1, n, m);
}