백준 14500 테트로미노

- 브루트포스 문제인데 정말 무식한 문제이다.. 다시는 풀기 싫은 문제

 

- 시간복잡도는 O(NM)이다. 

 

- 모든 가능한 블럭의 경우의 수를 먼저 생각하고, 이들이 주어진 범위에 어떻게 들어갈 수 있는지를 생각하면 된다. 꼼꼼하게 오류 없이 푸는게 중요한 것 같다.

/* 모든 경우의 수를 다 고려한다 */
#include <iostream>
using namespace std;
int a[500][500];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i<n; i++) {
		for (int j = 0; j<m; j++) {
			cin >> a[i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i<n; i++) {
		for (int j = 0; j<m; j++) {
			if (j + 3 < m) { // 가로 막대기
				int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i][j + 3];
				if (ans < temp) ans = temp;
			}
			if (i + 3 < n) { // 세로 막대기
				int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 3][j];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j + 2 < m) { // ㄴ 가로로 긴 것
				int temp = a[i][j] + a[i + 1][j] + a[i + 1][j + 1] + a[i + 1][j + 2];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j + 1 < m) { // ㄱ 좌우 대칭해서 세로로 긴 것
				int temp = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 2][j];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j + 2 < m) {  //ㄱ 가로로 긴 것
				int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i + 1][j + 2];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j - 1 >= 0) { // ㄴ 좌우 대칭해서 세로로 긴 것
				int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 2][j - 1];
				if (ans < temp) ans = temp;
			}
			if (i - 1 >= 0 && j + 2 < m) {  // ㄴ 좌우 대칭해서 가로로 긴 것
				int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i - 1][j + 2];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j + 1 < m) { // ㄴ 세로로 긴 것
				int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 2][j + 1];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j + 2 < m) { // ㄱ 좌우 대칭해서 가로로 긴 것
				int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i + 1][j];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j + 1 < m) { // ㄱ 세로로 긴 것
				int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i + 2][j + 1];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j + 1 < m) { // 네모
				int temp = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
				if (ans < temp) ans = temp;
			}
			if (i - 1 >= 0 && j + 2 < m) { // 번개 오른쪽 90도 회전
				int temp = a[i][j] + a[i][j + 1] + a[i - 1][j + 1] + a[i - 1][j + 2];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j + 1 < m) { // 번개
				int temp = a[i][j] + a[i + 1][j] + a[i + 1][j + 1] + a[i + 2][j + 1];
				if (ans < temp) ans = temp;
			}
			if (i + 1 < n && j + 2 < m) { // 번개 왼쪽 90도 회전
				int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i + 1][j + 2];
				if (ans < temp) ans = temp;
			}
			if (i + 2 < n && j - 1 >= 0) { // 번개 좌우 대칭
				int temp = a[i][j] + a[i + 1][j] + a[i + 1][j - 1] + a[i + 2][j - 1];
				if (ans < temp) ans = temp;
			}
			if (j + 2 < m) { 
				int temp = a[i][j] + a[i][j + 1] + a[i][j + 2];
				if (i - 1 >= 0) { // 가운데 중지 욕
					int temp2 = temp + a[i - 1][j + 1];
					if (ans < temp2) ans = temp2;
				}
				if (i + 1 < n) { // 가운데 중지 욕에서 중지 아래로
					int temp2 = temp + a[i + 1][j + 1];
					if (ans < temp2) ans = temp2;
				}
			}
			if (i + 2 < n) { // 가운데 중지 욕 90도 회전
				int temp = a[i][j] + a[i + 1][j] + a[i + 2][j];
				if (j + 1 < m) {
					int temp2 = temp + a[i + 1][j + 1];
					if (ans < temp2) ans = temp2;
				}
				if (j - 1 >= 0) { // 가운데 중지 욕 왼쪽 회전
					int temp2 = temp + a[i + 1][j - 1];
					if (ans < temp2) ans = temp2;
				}
			}
		}
	}
	cout << ans << '\n';
	return 0;
}