백준 14500 테트로미노

삼성 역량 기출문제 테트로미노 문제이다.

 

생각보다 쉬워서 놀랐고, 삼성 기출문제나 다른 코테 문제 수준이 딱 이 정도만 나오면 좋을 것 같단 생각이 들었다..

 

일단, tetromino라는 블록에 대한 배열을 다 만들었다.

5개의 블록을 회전 및 대칭을 시켰을 때 생성될 수 있는 경우는 총 19개가 된다.

그렇게 많지 않기 때문에 배열을 사용해서 19개의 모양을 나타내는 배열을 다 생성했다.

 

그리고 보드의 너비는 최대 500 x 500이지만, 만약 테트로미노가 겹쳐진다고 생각했을 때, 503까지 늘어날 수 있기 때문에 503 x 503의 사이즈로 생성해주었다.

 

그 다음으로는 너무 쉬웠다.

 

주어진 입력을 받아서 BOARD를 초기화하고, 좌상단에서 우하단까지 모든 좌표를 방문하면서 그 좌표 위에 올라갈 19개 테트로미노와 곱해준 뒤 가장 크게 계산되는 값을 반환해주고 출력해주면 끝이 난다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <stdlib.h>
#include <string.h>

using namespace std;

const int tetromino[19][4][4] = {
	{1, 1, 1, 1,
	 0, 0, 0, 0,
	 0, 0, 0, 0,
	 0, 0, 0, 0},
	{1, 0, 0, 0,
	 1, 0, 0, 0,
	 1, 0, 0, 0,
	 1, 0, 0, 0},
	{1, 1, 0, 0,
	 1, 1, 0, 0,
	 0, 0, 0, 0,
	 0, 0, 0, 0},
	{1, 0, 0, 0,
	 1, 0, 0, 0,
	 1, 1, 0, 0,
	 0, 0, 0, 0},
	{0, 0, 1, 0,
	 1, 1, 1, 0,
	 0, 0, 0, 0,
	 0, 0, 0, 0},
	{1, 1, 0, 0,
	 0, 1, 0, 0,
	 0, 1, 0, 0,
	 0, 0, 0, 0},
	{1, 1, 1, 0,
	 1, 0, 0, 0,
	 0, 0, 0, 0,
	 0, 0, 0, 0},
	{0, 1, 0, 0,
	 0, 1, 0, 0,
	 1, 1, 0, 0,
	 0, 0, 0, 0},
	{1, 1, 1, 0,
	 0, 0, 1, 0,
	 0, 0, 0, 0,
	 0, 0, 0, 0},
	{1, 1, 0, 0,
	 1, 0, 0, 0,
	 1, 0, 0, 0,
	 0, 0, 0, 0},
	{1, 0, 0, 0,
	 1, 1, 1, 0,
	 0, 0, 0, 0,
	 0, 0, 0, 0},
	{1, 0, 0, 0,
	 1, 1, 0, 0,
	 0, 1, 0, 0,
	 0, 0, 0, 0},
	{0, 1, 1, 0,
	 1, 1, 0, 0,
	 0, 0, 0, 0,
	 0, 0, 0, 0},
	{0, 1, 0, 0,
	 1, 1, 0, 0,
	 1, 0, 0, 0,
	 0, 0, 0, 0},
	{1, 1, 0, 0,
	 0, 1, 1, 0,
	 0, 0, 0, 0,
	 0, 0, 0, 0},
	{1, 1, 1, 0,
	 0, 1, 0, 0,
	 0, 0, 0, 0,
	 0, 0, 0, 0},
	{1, 0, 0, 0,
	 1, 1, 0, 0,
	 1, 0, 0, 0,
	 0, 0, 0, 0},
	{0, 1, 0, 0,
	 1, 1, 1, 0,
	 0, 0, 0, 0,
	 0, 0, 0, 0},
	{0, 1, 0, 0,
	 1, 1, 0, 0,
	 0, 1, 0, 0,
	 0, 0, 0, 0} };

int BOARD[503][503] = { 0, };

int multiply(int board_x, int board_y) {
	int res = 0;
	
	for (int t = 0; t < 19; ++t) {
		int temp_sum = 0;
		for (int y = 0; y < 4; ++y) {
			for (int x = 0; x < 4; ++x) {
				temp_sum += BOARD[board_y + y][board_x + x] * tetromino[t][y][x];
			}
		}

		if (temp_sum > res) {
			res = temp_sum;
		}
	}

	return res;
}

int main() {
	int N, M;
	scanf("%d %d", &N, &M);

	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			scanf("%d", &BOARD[y][x]);
		}
	}

	int max = 0;
	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			int temp = multiply(x, y);
			if (max < temp) {
				max = temp;
			}
		}
	}

	printf("%d", max);
	
	return 0;
}