[백준/BOJ] 백준 5463번 : 건포도

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

5463번: 건포도

 

2차원 누적합을 이용하여 각 구간의 건포도의 개수를 나타내었고, cache[x1][y1][x2][y2]에 (x1, y1) ~ (x2, y2) 직사각형을 자를 때 건포도의 최소 양을 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<vector<int>> board(51, vector<int>(51, 0));
vector<vector<int>> psum(51, vector<int>(51, 0)); //(2차원 누적합), psum[a][b] = ((1,1)에서 (a,b)위치 까지 합)
int cache[51][51][51][51]; //cache[x1][y1][x2][y2] = (x1,y1) ~ (x2,y2) 직사각형을 자를때 건포도의 최소 양

void Pre()
{
	for (int i = 0; i < 51; i++)
		for (int j = 0; j < 51; j++)
			for (int k = 0; k < 51; k++)
				for (int l = 0; l < 51; l++)
					cache[i][j][k][l] = -1;
}

//2차원 누적합 만들기
void MakePsum()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			psum[i][j] = psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1] + board[i][j];
		}
}

//(x1,y1) ~ (x2,y2) 직사각형을 자를때 건포도의 최소 양 구하기
int Solve(int x1, int y1, int x2, int y2)
{
	if (x1 == x2 && y1 == y2)
		return 0;

	int& ret = cache[x1][y1][x2][y2];

	if (ret != -1)
		return ret;

	ret = 987654321;

	//(x1,y1) ~ (x2,y2) 직사각형안의 건포도의 개수
	int this_add = psum[x2][y2] - psum[x2][y1 - 1] - psum[x1 - 1][y2] + psum[x1 - 1][y1 - 1];

	//가로로 자를때 경우의 수 확인
	for (int i = x1; i < x2; i++)
	{
		ret = min(ret, this_add + Solve(x1, y1, i, y2) + Solve(i + 1, y1, x2, y2));
	}

	//세로로 자를때 경우의 수 확인
	for (int j = y1; j < y2; j++)
	{
		ret = min(ret, this_add + Solve(x1, y1, x2, j) + Solve(x1, j + 1, x2, y2));
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}

	MakePsum();

	cout << Solve(1, 1, n, m) << "\n";

	return 0;
}