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

문제

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

예제 입력 1

5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

예제 출력 1

19

예제 입력 2

4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

예제 출력 2

20

알고리즘 [ 접근 방법 ]

아주아주 성가신 브루트 포스 문제이다.

놓을 수 있는 테트리스 도형의 종류는 5가지이고 회전이나 대칭이 가능하다 했으므로 총 가능한 테트리스 도형은 19종류이다.

이때 N(세로크기)<=4이고 M(가로크기)<=500 이므로 테트리스를 놓을수 있는 공간은 총 4x500=2000개가 된다.

대충 테트리스 종류 19가지 x 놓을수 있는 공간 2000 만 해도 큰 수가 아니므로 모든 경우의 수를 다 해보는 브루트 포스 문제라는 것을 유추할 수 있다.

이제 남은건 단순 구현이다.

가능한 19가지 경우를 전부 for문에 넣어주면 된다.

풀이

#include <iostream>


using namespace std;
int tet[501][501];

int main() {
	// cin의 연산시간을 scanf만큼 줄여주기 위한 코드 2줄
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	int m;

	cin >> n;
	cin >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> tet[i][j];
		}
	}
	int max = 0;
	int temp = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (j <= m - 3) { // ㅡㅡㅡㅡ
				temp = tet[i][j] + tet[i][j + 1] + tet[i][j + 2] + tet[i][j + 3];
				if (max < temp) max = temp;
			}
			if (i <= n - 3) { // 일자
				temp = tet[i][j] + tet[i + 1][j] + tet[i + 2][j] + tet[i + 3][j];
				if (max < temp) max = temp;
			}
			if (i <= n - 1 && j <= m - 1) { // ㅁ
				temp = tet[i][j] + tet[i][j + 1] + tet[i + 1][j] + tet[i + 1][j + 1];
				if (max < temp) max = temp;
			}
			if (i <= n - 2 && j <= m - 1) { // └
				temp = tet[i][j] + tet[i + 1][j] + tet[i + 2][j] + tet[i + 2][j + 1];
				if (max < temp) max = temp;
			}

			if (i <= n - 1 && j <= m - 2) { // ┌
				temp = tet[i][j] + tet[i][j + 1] + tet[i][j + 2] + tet[i + 1][j];
				if (max < temp) max = temp;
			}
			if (i <= n - 2 && j <= m - 1) { // ┐
				temp = tet[i][j] + tet[i][j + 1] + tet[i + 1][j + 1] + tet[i + 2][j + 1];
				if (max < temp) max = temp;
			}
			if (i >= 2 && j <= m - 2) { // ┘
				temp = tet[i][j] + tet[i][j + 1] + tet[i][j + 2] + tet[i - 1][j + 2];
				if (max < temp) max = temp;
			}
			if (i >= 3 && j <= m - 1) { // ┘
				temp = tet[i][j] + tet[i][j + 1] + tet[i - 1][j + 1] + tet[i - 2][j + 1];
				if (max < temp) max = temp;
			}
			if (i <= n - 1 && j <= m - 2) { // ┐
				temp = tet[i][j] + tet[i][j + 1] + tet[i][j + 2] + tet[i + 1][j + 2];
				if (max < temp) max = temp;
			}
			if (i <= n - 2 && j <= m - 1) { // ┌
				temp = tet[i][j] + tet[i + 1][j] + tet[i + 2][j] + tet[i][j + 1];
				if (max < temp) max = temp;
			}
			if (i <= n - 1 && j <= m - 2) { // ㄴ
				temp = tet[i][j] + tet[i + 1][j] + tet[i + 1][j + 1] + tet[i + 1][j + 2];
				if (max < temp) max = temp;
			}
			if (i <= n - 2 && j <= m - 1) { // └┐
				temp = tet[i][j] + tet[i + 1][j] + tet[i + 1][j + 1] + tet[i + 2][j + 1];
				if (max < temp) max = temp;
			}
			if (i >= 2 && j <= m - 1) { // 
				temp = tet[i][j] + tet[i][j + 1] + tet[i - 1][j + 1] + tet[i - 1][j + 2];
				if (max < temp) max = temp;
			}
			if (i >= 3 && j <= m - 1) { // ┌┘
				temp = tet[i][j] + tet[i - 1][j] + tet[i - 1][j + 1] + tet[i - 2][j + 1];
				if (max < temp) max = temp;
			}
			if (i <= n - 1 && j <= m - 1) { // ㄱㄴ
				temp = tet[i][j] + tet[i][j + 1] + tet[i + 1][j + 1] + tet[i + 1][j + 2];
				if (max < temp) max = temp;
			}
			if (i >= 2 && j <= m - 1) { // ㅗ
				temp = tet[i][j] + tet[i][j + 1] + tet[i - 1][j + 1] + tet[i][j + 2];
				if (max < temp) max = temp;
			}
			if (i <= n - 2 && j <= m - 1) { // ㅏ
				temp = tet[i][j] + tet[i + 1][j] + tet[i + 1][j + 1] + tet[i + 2][j];
				if (max < temp) max = temp;
			}
			if (i <= n - 1 && j <= m - 2) { // ㅜ
				temp = tet[i][j] + tet[i][j + 1] + tet[i + 1][j + 1] + tet[i][j + 2];
				if (max < temp) max = temp;
			}
			if (i >= 2 && i <= n - 1 && j <= m - 1) { // ㅓ
				temp = tet[i][j] + tet[i][j + 1] + tet[i - 1][j + 1] + tet[i + 1][j + 1];
				if (max < temp) max = temp;
			}
		}
	}

	cout << max << endl;

}