[백준 14500] 테트로미노 C++ 노가다풀이

# 문제링크

www.acmicpc.net/problem/14500

14500번: 테트로미노

DFS 등등 활용해서 계산할 수도 있겠지만 문제를 보니 경우의 수가 몇 가지 되지 않을 것 같았다. 누적합을 활용해서 직접 모든 경우의 수를 직접 구해줘도 되지 않을까 하는 생각이 들었고, O(n^2) 시간 안에 해결할 수 있을 거 같았다. 개껌이네 생각하고 노가다를 시작했다.. (역시 머리가 안좋으면 몸이 고생한다고 내 손이 고생했다.) 코테를 볼 때에도 머리가 안되면 재빨리 노가다라도 해서 통과할거다 ㅠㅠㅠㅠㅠ 흑흑 다 풀고 검색해보니 나처럼 무식하게 푼 사람은 정말 없는듯 ㅋㅋㅋㅋㅋㅋㅋ 제 코드 보시고 맘껏 웃으세요....  

 

범위 계산하기 귀찮아서 그냥 배열을 조금 크게 줬다. 원래 500 사이즈인데 좌우에 padding 5씩 생각해서 510 을 줬다. 어차피 최대값을 구하는 거라, 삐져나가는 부분은 0으로 답을 구하는 데에는 상관이 없었다.

 

# 제출 코드 

 

#include <cstdio>
#include <cstring>
using namespace std;

int map[510][510];
int N, M;
int sum_v[510][510]; // 수직(세로) 누적합
int sum_h[510][510]; // 수평(가로) 누적합
int ans = -1;

void Input() {
	scanf("%d %d", &N, &M); // N: 세로, M : 가로
	for (int i = 5; i < N + 5; i++) {
		for (int j = 5; j < M + 5; j++) {
			scanf("%d", &map[i][j]);
			sum_v[i][j] = sum_v[i - 1][j] + map[i][j];
			sum_h[i][j] = sum_h[i][j - 1] + map[i][j];
		}
	}
}
void Solve() {
	int tmp;
	for (int i = 5; i < N + 5; i++) {
		for (int j = 5; j < M + 5 ; j++) {
			// 가로 확인 
			// 두 개가 일직선 -> 5가지 경우			
			tmp = sum_h[i][j + 1] - sum_h[i][j - 1];

			if (tmp + sum_h[i + 1][j + 1] - sum_h[i + 1][j - 1] > ans) ans = tmp + sum_h[i + 1][j + 1] - sum_h[i + 1][j - 1];

			if (tmp + sum_h[i + 1][j] - sum_h[i + 1][j - 2] > ans) ans = tmp + sum_h[i + 1][j] - sum_h[i + 1][j - 2];
			if (tmp + sum_h[i + 1][j + 2] - sum_h[i + 1][j] > ans) ans = tmp + sum_h[i + 1][j + 2] - sum_h[i + 1][j];


			// 세 개 일직선 -> 6가지 경우
			tmp = sum_h[i][j + 2] - sum_h[i][j - 1];
			
			if (tmp + map[i - 1][j] > ans) ans = tmp + map[i - 1][j];
			if (tmp + map[i - 1][j + 1] > ans) ans = tmp + map[i - 1][j + 1];
			if (tmp + map[i - 1][j + 2] > ans) ans = tmp + map[i - 1][j + 2];
			
			if (tmp + map[i + 1][j] > ans) ans = tmp + map[i + 1][j];
			if (tmp + map[i + 1][j + 1] > ans) ans = tmp + map[i + 1][j + 1];
			if (tmp + map[i + 1][j + 2] > ans) ans = tmp + map[i + 1][j + 2];


			//네 개 일직선 -> 1가지 경우
			tmp = sum_h[i][j + 3] - sum_h[i][j - 1];
			if (tmp > ans) ans = tmp;

			// 세로 확인 
			// 두 개가 일직선
			tmp = sum_v[i + 1][j] - sum_v[i - 1][j];

			if (tmp + sum_v[i][j + 1] - sum_v[i - 2][j + 1] > ans) ans = tmp + sum_v[i][j + 1] - sum_v[i - 2][j + 1];
			if (tmp + sum_v[i + 2][j + 1] - sum_v[i][j + 1] > ans) ans = tmp + sum_v[i + 2][j + 1] - sum_v[i][j + 1];

			// 세 개 일직선 -> 6가지 경우
			tmp = sum_v[i + 2][j] - sum_v[i - 1][j];

			if (tmp + map[i][j - 1] > ans) ans = tmp + map[i][j - 1];
			if (tmp + map[i + 1][j - 1] > ans) ans = tmp + map[i + 1][j - 1];
			if (tmp + map[i + 2][j - 1] > ans) ans = tmp + map[i + 2][j - 1];

			if (tmp + map[i][j + 1] > ans) ans = tmp + map[i][j + 1];
			if (tmp + map[i + 1][j + 1] > ans) ans = tmp + map[i + 1][j + 1];
			if (tmp + map[i + 2][j + 1] > ans) ans = tmp + map[i + 2][j + 1];


			//네 개 일직선 -> 1가지 경우
			tmp = sum_v[i + 3][j] - sum_v[i - 1][j];
			if (tmp > ans) ans = tmp;

		}
	}
}
int main() {
	//freopen("sample_input.txt", "r", stdin);
	Input();
	Solve();
	printf("%d\n", ans);
}

 

 

 

노가다결과..