14500 테트로미노

 

위의 사진은 5가지의 테트로미노입니다 해당 테트로미노를 2차원 배열 위에 올렸을때 테트로미노 범위 안의 합이 

가장 큰 값을 구하는겁니다.

 

여기까지는 해당 테트로미노의 좌표값을 구해 반복문을 돌리면 쉽게 풀 수 있습니다.

하지만 테트로미노는 회전 및 대칭을 할 수 있어서 생각을 좀 하게 되는 문제입니다.

만약 하늘색 첫번째 테트로미노를 예를 들어서 설명한다면 위치는 {0,0}, {0,1}, {0,2}, {0,3} 이 될 겁니다.

시계방향으로 90도로 회전한다면 어떻게 될까요 {0, 0}, {1,0}, {2, 0}, {3,0} 입니다.

x의 위치와 y의 위치를 바꾼것과 동일합니다, 여기서 또 문제가 발생합니다 만약 시계반대 방향으로 90도 돌아간다면 어떻게 될까 {0,0}, {-1,0} {-2, 0}, {-3,0}이 되겠습니다. 그럼 우리는 시계방향으로 회전한 것을 x에  -1만곱해주면 시계반대방향으로 회전하는것과 같다는 것을 알 수 있습니다. 각도는 총 크게 0, 90, 180, 270도로 x와 y에 모두 1을 곱해주면 0도

x만 -1을 곱해주면 90도, y만 -1을 곱해주면 180도, x와 y의 모두 -1을 곱해주면 270도가 됩니다. 

 

4방향 중 최대값을 찾습니다.

maxs = max(maxs, sum(i,j,1,1));
maxs = max(maxs, sum(i,j,1,-1));
maxs = max(maxs, sum(i,j,-1,1));
maxs = max(maxs, sum(i,j,-1,-1));

 

결론: 4방향을 바꿔주면서 x와 y를 바꿔주면서 대칭 되는 경우도 찾아낸다.

 

#include <iostream>

using namespace std;


int dx[20] = {0, 1, 2, 2, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 0, 1, 0, 0, 1, 1};
int dy[20] = {0, 0, 0, 1, 0, 1, 2, 3, 0, 0, 1, 1, 0, 1, 2, 1, 0, 1, 0, 1};


int n,m;
int board[501][501];
	
int sum(int i, int j, int mx, int my) {
	int sum = 0;
	int maxs = 0;
	
	int nx, ny;
	

	for(int k = 0; k < 20; k++) {
		
		if(k % 4 == 0) {
	    	maxs = max(maxs, sum);
			sum = 0;
		}
		
		nx = i + dx[k] * mx;
		ny = j + dy[k] * my;
		
		if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
		
		sum+= board[nx][ny];
	}	
	
	maxs = max(maxs, sum);
	sum = 0;

	for(int k = 0; k < 20; k++) {
		if(k % 4 == 0) {
			maxs = max(maxs, sum);
			sum = 0;
		}
		
		nx = i + dy[k] * mx;
		ny = j + dx[k] * my;
		
		if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
		
		sum+= board[nx][ny];
		
	}
	maxs = max(maxs, sum);


	
	return maxs;
	
}

int check(int i, int j) {
	int maxs = 0;
	
	maxs = max(maxs, sum(i,j,1,1));
	maxs = max(maxs, sum(i,j,1,-1));
	maxs = max(maxs, sum(i,j,-1,1));
	maxs = max(maxs, sum(i,j,-1,-1));
	
	
	return maxs;
	
}

int main() {

	ios_base::sync_with_stdio(false);
	
	cin.tie(NULL);
	cout.tie(NULL);
	

	cin >> n >> m;
	
	
	
	for(int i = 0; i < n; i++) {
		
		for(int j = 0; j < m; j++){
			cin >> board[i][j];
		}
	}
	
	int maxs = 0;
	int nx, ny;
	
	for(int i = 0; i < n; i++) {

		for(int j = 0; j < m; j++){
			maxs = max(maxs, check(i,j));
		}
	}	
	
	cout << maxs;
	
	
}