[Baekjoon][C++] 14500번 테트로미노 문제설명 및 코드

14500번: 테트로미노

▷ 문제설명

NxM 크기의 종이 위에 테트로미노를 하나 놓아서 놓인 칸에 쓰여 있는 수의 합을 최대로 하는 문제

N, M의 범위는 4 <= N, M <= 500 이다.

 

▷ 문제풀이

테트로미노를 회전 및 대칭하여 미리 행렬로 표현(19개)하고 NxM 종이 위에 놓고 MAX 값을 찾는 방법으로 해결한다.

 

즉,

(0,0)

(0,1)

(0,2)

(0,3)

=> {{0,0}, {0,1}, {0,2}, {0,3}}

 

1) 위와 같이 놓을 수 있는 테트로미노를 3차 행렬로 표현한다. 회전 및 대칭을 포함해서 총 19개

2) NxM 종이의 0,0 좌표부터 탐색을 시작한다.

3) 행렬로 표현한 테트로미노 19개 중 하나를 선택해서 NxM 종이에 놓는다.

4) 이 때, 테트로미노를 한 좌표씩 놓으면서 테트로미노가 놓인 곳이 행렬의 x, y값의 범위를 벗어나는지 확인한다.

5) 범위 안에 있으면 한 좌표씩 SUM값에 저장한다.

6) 4칸 모두 행렬에 놓아지면 SUM값과 MAX값을 비교한다.

6) 마지막 좌표까지 확인하고 최종 MAX값을 출력한다.

▷ 시간복잡도

테트로미노는 총 19가지가 있고, 하나의 테트로미노당 놓을 수 있는 방법의 개수는 약 O(NM)가지이다.

즉, NxM 종이에 19개의 도형을 올리는 경우의 수는 O(19*N*M) = O(N^2)의 시간복잡도를 가진다.

 

▷ 정답코드

#include <iostream>
#include<algorithm>
#define SIZE 500
using namespace std;

void Input();
void StartCalculation(int arr[SIZE][SIZE], int N, int M);

int main() {
	Input();
}

void Input() {
	int N, M;
	int arr[SIZE][SIZE] = { {0,0}, };

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

void StartCalculation(int arr[SIZE][SIZE], int N, int M) {
	int tetro[19][4][2] = {
		// □□□□
		{{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,0}, {1,0}, {0,1}, {0,2}},
		{{0,0}, {0,1}, {1,1}, {2,1}},
		{{0,0}, {1,0}, {2,0}, {2,-1}},
		{{0,0}, {0,1}, {0,2}, {-1,2}},
		{{0,0}, {1,0}, {2,0}, {0,1}},
		{{0,0}, {1,0}, {1,1}, {1,2}},
		{{0,0}, {0,1}, {0,2}, {1,2}},
		// □
		// □□
		//  □
		{{0,0}, {1,0}, {1,1}, {2,1}},
		{{0,0}, {1,0}, {-1,1} , {0,1}},
		{{0,0}, {0,1}, {-1,1}, {-1,2}},
		{{0,0}, {0,1}, {1,1}, {1,2}},
		// □□□
		//  □
		{{0,0}, {0,1}, {0,2}, {1,1}},
		{{0,0}, {1,-1}, {1,0}, {1,1}},
		{{0,0}, {1,0}, {2,0}, {1,1}},
		{{0,0}, {1,0}, {2,0}, {1,-1}},
	};

	int answer = 0;
	for (int i = 0; i < N; i++) {//N행
		for (int j = 0; j < M; j++) {//M열
			for (int k = 0; k < 19; k++) {//모양 19개 하나씩 선택하기
				int sum = 0;
				for (int l = 0; l < 4; l++) {//선택한 블럭모양 한 칸씩 값 더하기
					int x = i + tetro[k][l][0];//현재 위치의 x값 + k모양 1칸에 해당하는 x값
					int y = j + tetro[k][l][1];//현재 위치의 y값 + k모양 1칸에 해당하는 y값
					if (0 <= x && N > x && 0 <= y && M > y) {//x,y값이 범위를 벗어나는지 확인
						sum += arr[x][y];//범위안에 있으면 sum값으로 더하기
					}
					else {//범위를 벗어나버리면 바로 나와서 다음 모양 탐색하기
						break; 
					}
				}
				answer = max(answer, sum);//정상적으로 더한 값이 현재까지의 max 값보다 크면 값 체인지
			}
		}
	}
	cout << answer << '\n';
}