[백준 14500] 테트로미노

문제 바로가기

14500번: 테트로미노

테트로미노를 이루는 도형들의 좌표를 tetromino 배열에 넣어서 완전탐색으로 구현하였다.

 

처음에는 5개의 테트로미노만 배열에 넣고 회전이나 대칭시키는 것을 for문 내에서 하려고 했는데,

코드가 너무 어려워질 것 같아서 회전, 대칭 시켰을 때 모양이 겹치지 않는 19개의 테트로미노를 직접 구했다.

이 19개의 좌표를 모두 넣는 것이 상당한 노가다,, 

좌표 넣으면서 실수해서 푸는 데 시간이 좀 걸렸다.

 

코드 내에 for문이 무려 4중 포문이였지만 시간초과가 뜨진 않았다 ㅎ

어차피 완전탐색으로밖에 구현이 안될 것 같은데 다른 방법이 있을까..?

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;
int arr[500][500];
pair<int, int> tetromino[19][4]
= { {{0,0},{0,1},{0,2},{0,3}},{{0,0},{1,0},{2,0},{3,0}},{{0,0},{1,0},{0,1},{1,1}},
{{0,0},{1,0},{2,0},{2,1}},{{0,1},{1,1},{2,1},{2,0}},{{1,0},{1,1},{1,2},{0,2}},{{0,0},{1,0},{1,1},{1,2}},
{{0,0},{0,1},{1,0},{2,0}},{{0,0},{0,1},{1,1},{2,1}},{{0,0},{0,1},{0,2},{1,0}}, {{0,0},{0,1},{0,2},{1,2}},
{{0,0},{1,0},{1,1},{2,1}},{{0,1},{1,1},{1,0},{2,0}}, {{1,0},{1,1},{0,1},{0,2}}, {{0,0},{0,1},{1,1},{1,2}},
{{0,0},{0,1},{0,2},{1,1}},{{1,0},{1,1},{1,2},{0,1}},{{0,0},{1,0},{2,0},{1,1}},{{0,1},{1,1},{2,1},{1,0}} };

int max_sum;
bool isIn(int y, int x)
{
	if (x >= 0 && x < M && y >= 0 && y < N)
		return true;
	return false;
}
int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
		}
	}

	for (int n = 0; n < 19; n++)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				pair<int, int> tmp[4];
				int sum = 0;
				for (int k = 0; k < 4; k++)
				{
					tmp[k] = { i + tetromino[n][k].first, j + tetromino[n][k].second };
					
					if (!isIn(tmp[k].first, tmp[k].second))
					{
						sum = 0;
						break;
					}
					sum += arr[tmp[k].first][tmp[k].second];
				}
				max_sum = max(sum, max_sum);
			}
		}
	}

	cout << max_sum << endl;
	return 0;
}