[백준] 14500번 테트로미노 - C++

---

테트로미노

 N x M 크기의 보드에 정사각형 4개로 이루어진 블록을 무작위로 배치했을 때 블록에 가려진 정수의 합이 가장 큰 경우의 값을 찾는 문제입니다. 어떻게 풀어야 하나.. 고민하다가 아이디어가 당장 안 떠올라서 노가다 - 멋있는 말로 브루트 포스 - 로 풀었습니다.

풀이방법

 그림과 같이 엑셀에 모든 블록의 경우의 수를 정리해 보니까 19가지의 블록을 최대 500 x 500의 보드에 배치하는 것이기 때문에 시간제한 2초 안에 성공할 수 있을 것 같아서 브루트포스를 선택했습니다. 그림과 같이 블록들을 가로 x 세로의 크기대로 분류하면 총 5가지의 유형으로 분류할 수 있습니다. 유형별로 2중 for문을 돌리고 for문 안에서 공통된 블록은 한 번만 계산함으로써 최대한 연산을 줄였습니다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	vector<vector<int>> paper(n, vector<int>(m));
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> paper[i][j];

	int max = 0;

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m - 3; ++j)
		{
			int sum = paper[i][j] + paper[i][j + 1] + paper[i][j + 2] + paper[i][j + 3];
			if (sum > max)
				max = sum;
		}
	}

	for (int i = 0; i < n - 3; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			int sum = paper[i][j] + paper[i + 1][j] + paper[i + 2][j] + paper[i + 3][j];
			if (sum > max)
				max = sum;
		}
	}

	for (int i = 0; i < n - 1; ++i)
	{
		for (int j = 0; j < m - 1; ++j)
		{
			int sum = paper[i][j] + paper[i][j + 1] + paper[i + 1][j] + paper[i + 1][j + 1];
			if (sum > max)
				max = sum;
		}
	}

	for (int i = 0; i < n - 2; ++i)
	{
		for (int j = 0; j < m - 1; ++j)
		{
			int left_bar = paper[i][j] + paper[i + 1][j] + paper[i + 2][j];

			int sum = left_bar + paper[i][j + 1];
			if (sum > max)
				max = sum;

			sum = left_bar + paper[i + 1][j + 1];
			if (sum > max)
				max = sum;

			sum = left_bar + paper[i + 2][j + 1];
			if (sum > max)
				max = sum;

			int right_bar = paper[i][j + 1] + paper[i + 1][j + 1] + paper[i + 2][j + 1];

			sum = right_bar + paper[i][j];
			if (sum > max)
				max = sum;

			sum = right_bar + paper[i + 1][j];
			if (sum > max)
				max = sum;

			sum = right_bar + paper[i + 2][j];
			if (sum > max)
				max = sum;

			int middle_bar = paper[i + 1][j] + paper[i + 1][j + 1];

			sum = middle_bar + paper[i][j] + paper[i + 2][j + 1];
			if (sum > max)
				max = sum;

			sum = middle_bar + paper[i][j + 1] + paper[i + 2][j];
			if (sum > max)
				max = sum;
		}
	}

	for (int i = 0; i < n - 1; ++i)
	{
		for (int j = 0; j < m - 2; ++j)
		{
			int upper_bar = paper[i][j] + paper[i][j + 1] + paper[i][j + 2];

			int sum = upper_bar + paper[i + 1][j];
			if (sum > max)
				max = sum;

			sum = upper_bar + paper[i + 1][j + 1];
			if (sum > max)
				max = sum;

			sum = upper_bar + paper[i + 1][j + 2];
			if (sum > max)
				max = sum;

			int lowwer_bar = paper[i + 1][j] + paper[i + 1][j + 1] + paper[i + 1][j + 2];

			sum = lowwer_bar + paper[i][j];
			if (sum > max)
				max = sum;

			sum = lowwer_bar + paper[i][j + 1];
			if (sum > max)
				max = sum;

			sum = lowwer_bar + paper[i][j + 2];
			if (sum > max)
				max = sum;

			int middle_bar = paper[i][j + 1] + paper[i + 1][j + 1];

			sum = middle_bar + paper[i][j] + paper[i + 1][j + 2];
			if (sum > max)
				max = sum;

			sum = middle_bar + paper[i][j + 2] + paper[i + 1][j];
			if (sum > max)
				max = sum;
		}
	}

	cout << max;

	return 0;
}

마치며

 다풀고 다른 사람의 풀이도 보고 복기해 보니 dfs로도 풀 수 있지만 의외로 브루트포스가 메모리도 덜 쓰고 성능도 좋았습니다. 하지만 dfs로 풀면 멋있기 때문에 멋쟁이 분들은 dfs로 도전해 보셔도 좋을 것 같습니다.