백준 - 게리맨더링 2 (17779번)

백준 - 게리맨더링 2 (17779번)

배열 범위 생각하기가 힘들거나 귀찮다면 그냥 문제에서 주어진 조건 그대로 적어도 맞출 수 있는 문제다.
단, 쓸모없는 연산을 좀 할테니 속도는 제일 빠르진않다.

코드는 아래와 같다.

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int n;
int map[128][128];
int tmp[128][128];

int making_election_area(int x, int y, int d1, int d2)
{
	vector<int> area(5, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (1 <= i && i < x + d1 && 1 <= j && j <= y) 
				tmp[i][j] = 1;
			else if (1 <= i && i <= x + d2 && y < j && j <= n) 
				tmp[i][j] = 2;
			else if (x + d1 <= i && i <= n && 1 <= j && j < y - d1 + d2) 
				tmp[i][j] = 3;
			else if (x + d2 < i && i <= n && y - d1 + d2 <= j && j <= n) 
				tmp[i][j] = 4;
		}
	}
	for (int i = 0; i <= d1; i++) 
		tmp[x + i][y - i] = 5;
	for (int i = 0; i <= d2; i++) 
		tmp[x + i][y + i] = 5;
	for (int i = 0; i <= d2; i++) 
		tmp[x + d1 + i][y - d1 + i] = 5;
	for (int i = 0; i <= d1; i++) 
		tmp[x + d2 + i][y + d2 - i] = 5;
	
	for (int i = 1; i <= n; i++) {
		int start = 0, end = 0;
		for (int j = 1; j <= n; j++) {
			if (tmp[i][j] == 5) {
				start = j;
				break;
			}
		}
		for (int j = n; j >= 1; j--) {
			if (tmp[i][j] == 5) {
				end = j;
				break;
			}
		}
		for (int j = start; j <= end; j++) 
			tmp[i][j] = 5;
	}

	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= n; j++) 
			area[tmp[i][j] - 1] += map[i][j];

	int max_value = *max_element(area.begin(), area.end());
	int min_value = *min_element(area.begin(), area.end());
	int diff = max_value - min_value;

	return diff;
}
int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int answer = 1 << 20;

	cin >> n;
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= n; j++) 
			cin >> map[i][j];
	
	int d1, d2, x, y;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			x = i; y = j;
			for (int p = 1; p <= n; p++) {
				for (int q = 1; q <= n; q++) {
					d1 = p; d2 = q;
					if (d1 < 1 || d2 < 1)
						continue;
					if (1 > x || x >= x + d1 + d2 || x + d1 + d2 > n)
						continue;
					if (1 > y - d1 || y - d1 >= y || y >= y + d2 || y + d2 > n)
						continue;
					answer = min(answer, making_election_area(x, y, d1, d2));
				}
			}
		}
	}

	cout << answer << "\n";

	return 0;
}