[BOJ]백준 14500번: 테트로미노

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

^- 문제링크

테트리스 블록들

테트리스 블록을 회전/대칭했을 때의 모양을 고려하여 배열에 덮었을 때 덮은 숫자의 최댓값!을 찾는 문제이다

 

ㅇㅖ를 들어, 예제 입력이 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 이라면

계단모양의 블록을 저 위치에 놓았을 때 6+5+4+3 = 19가 해당 입력에서 얻을 수 있는 최댓값이다.

 

답은 의외로 간단하다

모든 경우의 수 블록을 만들어놓고

판에 올리는 모든 경우를 계산하면 끝 ^^

블록은 위처럼 19개가 나올 수 있다

나는 한 칸을 기준 좌표로 잡고 나머지 칸은 좌표를 가감해줘서 배열에 저장했다

블록이 N*M 배열을 벗어나는 경우는 break해준다

 

#include <cstdio>
int n, m, arr[501][501],ans;
struct point { int r,c; };
point t[19][3] = {
	{{1,0},{2,0},{3,0}},
	{{0,1},{0,2},{0,3}},
	{{1,0},{0,1},{1,1}},
	{{1,0},{2,0},{2,1}},
	{{0,1},{1,1},{2,1}},
	{{0,1},{-1,1},{-2,1}},
	{{0,1},{1,0},{2,0}},
	{{1,0},{0,1},{-1,1}},
	{{0,1},{1,1},{1,2}},
	{{1,0},{1,1},{2,1}},
	{{0,1},{-1,1},{-1,2}},
	{{0,1},{1,1},{0,2}},
	{{-1,1},{0,1},{1,1}},
	{{0,1},{-1,1},{0,2}},
	{{1,0},{1,1},{2,0}},
	{{0,1},{0,2},{1,2}},
	{{-1,2},{0,1},{0,2}},
	{{1,0},{1,1},{1,2}},
	{{1,0},{0,1},{0,2}}
};
bool safe(int r, int c) {
	return r >= 0 && r < n && c >= 0 && c < m;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)scanf("%d", &arr[i][j]);
	for (int b = 0; b < 19; b++) {

		for(int i=0;i<n;i++)
			for (int j = 0; j < m; j++) {
				point p[3]; bool bk=false;
				int sum = arr[i][j];
				for (int k = 0; k < 3; k++) {
					p[k] = {i + t[b][k].r, j + t[b][k].c };
					if (!safe(p[k].r, p[k].c))bk = true;
				}
				if (bk)continue;
				for (int k = 0; k < 3; k++)
					sum += arr[p[k].r][p[k].c];
				if (sum > ans)ans = sum;
			}

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

시간복잡도 : O(n^2) (블록의 개수, 블럭좌표 계산은 상수값이므로 N과 M의 크기에 따라 결정)