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

www.acmicpc.net/problem/14500

14500번: 테트로미노

처음엔 경우의 수를 적게 생각하고 풀어서 계속 틀린 문제이다.

 

천천히 대칭을 포함한 경우의 수 19가지를 생각하고 그에 맞게 최대값을 구해주었다.

 

나 같은 경우에는 크게 5가지로 나누었다.

 

네모 모양 1가지 경우의 수를 계산하고

 

3개짜리 테트리스에 1개를 모든 방향에 붙인다는 생각으로 크게 2가지, 작게 7가지씩 14가지를 구성하였고

 

또한 2개짜리에 2개를 붙이는 경우를 2개씩 총 4가지를 계산해주었다.

#define _CRT_SECURE_NO_WARINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int map[501][501];
int N, M, ans, temp;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < N - 1; i++) {	// 네모모양 계산
		for (int j = 0; j < M - 1; j++) {
			ans = max(ans, map[i][j] + map[i + 1][j + 1] + map[i + 1][j] + map[i][j + 1]);
		}
	}
	for (int i = 0; i < N - 2; i++) {	//세로 3개짜리에 1개 붙이기
		for (int j = 0; j < M; j++) {
			temp = map[i][j] + map[i + 1][j] + map[i + 2][j];
			if (i + 3 < N) {
				ans = max(ans, temp + map[i + 3][j]);
			}
			if (j - 1 >= 0) {
				ans = max(ans, temp + map[i][j - 1]);
				ans = max(ans, temp + map[i + 1][j - 1]);
				ans = max(ans, temp + map[i + 2][j - 1]);
			}
			if (j + 1 < M) {
				ans = max(ans, temp + map[i][j + 1]);
				ans = max(ans, temp + map[i + 1][j + 1]);
				ans = max(ans, temp + map[i + 2][j + 1]);
			}
		}
	}
	for (int i = 0; i < N; i++) {	//가로 3개짜리에 1개 붙이기
		for (int j = 0; j < M - 2; j++) {
			temp = map[i][j] + map[i][j + 1] + map[i][j + 2];
			if (j + 3 < M) {
				ans = max(ans, temp + map[i][j + 3]);
			}
			if (i - 1 >= 0) {
				ans = max(ans, temp + map[i - 1][j]);
				ans = max(ans, temp + map[i - 1][j + 1]);
				ans = max(ans, temp + map[i - 1][j + 2]);
			}
			if (i + 1 < N) {
				ans = max(ans, temp + map[i + 1][j]);
				ans = max(ans, temp + map[i + 1][j + 1]);
				ans = max(ans, temp + map[i + 1][j + 2]);
			}
		}
	}
	for (int i = 0; i < N - 2; i++) {	//세로 2개짜리에 2개 붙이기
		for (int j = 0; j < M; j++) {
			temp = map[i][j] + map[i + 1][j];
			if (j - 1 >= 0) {
				ans = max(ans, temp + map[i+1][j - 1] + map[i + 2][j - 1]);
			}
			if (j + 1 < M) {
				ans = max(ans, temp + map[i+1][j + 1] + map[i + 2][j + 1]);
			}
		}
	}
	for (int i = 0; i < N; i++) {		//가로 2개짜리에 2개 붙이기
		for (int j = 0; j < M - 2; j++) {
			temp = map[i][j] + map[i][j + 1];
			if (i + 1 < N) {
				ans = max(ans, temp + map[i + 1][j + 1] + map[i + 1][j + 2]);
			}
			if (i - 1 >= 0) {
				ans = max(ans, temp + map[i - 1][j + 1] + map[i - 1][j + 2]);
			}
		}
	}
	cout << ans << "\n";
}