백준 17779 게리맨더링2

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

17779번: 게리맨더링 2

 

- 브루트포스 + 빡구현 문제이다.

 

- 시간복잡도는, 최악의 경우 거의 O(N^6)까지도 도달할 수 있다. 하지만 N의 최대값이 20이므로 1억 이하이기 때문에 해당 알고리즘으로 통과가 가능하다.

 

- 시작점 x,y와 모든 d1, d2에 대한 경우의 수들을 선택해서 계산을 해야 한다. 4중 for문으로 4가지 변수값을 선택했다면, area 배열에 구역을 입력 해 주면 된다. 일단

 

  1. 5번 경계점들을 넣어주고,

  2. 경계선 내부를 5로 채워주고

  3. 차례대로 나머지 구역들을 채워준다.

 

  여기서, 경계선 내부를 채워주는 연산을 잘 해야 하는데 왼쪽 위, 오른쪽 위는 y값을 기준으로, 왼쪽 아래, 오른쪽 아래는 y-d1+d2값을 기준으로 해서 5를 잘 채워주면 된다.

 

- 5번 구역만 잘 채워주면 쉽게 해결할 수 있는 문제이다. 

 

 

 

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

int man[21][21];
int area[21][21];
int n;

int getpartOne(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = 1; i < x + d1; i++) {
		for (int j = 1; j <= y; j++) {
			if (area[i][j] == 5) continue;
			sum += man[i][j];
		}
	}
	return sum;
}
int getpartTwo(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = 1; i <= x + d2; i++) {		
		for (int j = y + 1; j <= n; j++) {	
			if (area[i][j] == 5) continue;
			sum += man[i][j];
		}
	}
	return sum;
}
int getpartThree(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = x + d1; i <= n; i++) {		
		for (int j = 1; j < y - d1 + d2; j++) {
			if (area[i][j] == 5) continue;
			sum += man[i][j];

		}
	}
	return sum;
}
int getpartFour(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = x + d2 + 1; i <= n; i++) {
		for (int j = y - d1 + d2; j <= n; j++) {
			if (area[i][j] == 5) continue;
			sum += man[i][j];
		}
	}
	return sum;
}
void divide(int x, int y, int d1, int d2) {
	memset(area, 0, sizeof(area));
	area[x][y] = 5;
	//1
	int nx = x;
	int ny = y;
	for (int i = 0; i < d1; i++) {
		nx += 1; ny -= 1;
		if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
		for (int j = ny; j <= y; j++) {
			area[nx][j] = 5;
		}
	}
	//2
	nx = x;
	ny = y;
	for (int k = 0; k < d2; k++) {
		nx += 1; ny += 1;
		if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
		for (int j = y; j <= ny; j++) {
			area[nx][j] = 5;
		}
	}
	//3
	nx = x + d1;
	ny = y - d1;
	area[nx][ny] = 5;
	for (int k = 0; k < d2; k++) {
		nx += 1; ny += 1;
		area[nx][ny] = 5;
		for(int j = ny; j <= y - d1 + d2; j++){
			area[nx][j] = 5;
		}
	}
	nx = x + d2;
	ny = y + d2;
	area[nx][ny] = 5;
	for (int k = 0; k < d1; k++) {
		nx += 1; ny -= 1;
		if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
		for (int j = y-d1+d2; j <= ny; j++) {
			area[nx][j] = 5;
		}
	}
}
int main() {
	cin >> n;
	int total_arr = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> man[i][j];
			total_arr += man[i][j];
		}
	}
	//각 칸을 돌면서 기준점 정함
	int answer = 2100000000;
	for (int x = 1; x <= n; x++) {		//행
		for (int y = 1; y <= n; y++) {		//열
			for (int d1 = 1; d1 <= 20; d1++) {
				for (int d2 = 1; d2 <= 20; d2++) {
					if (x + d1 + d2 > n || y-d1<1 || y+d2 >n) break;
					divide(x, y, d1, d2);
					
					int sum1 = getpartOne(x, y, d1, d2);
					int sum2 = getpartTwo(x, y, d1, d2);
					int sum3 = getpartThree(x, y, d1, d2);
					int sum4 = getpartFour(x, y, d1, d2);
					int sum5 = total_arr - (sum1 + sum2 + sum3 + sum4);
					//각 선거구역 크기는 최소 1칸 이상
					if (sum1 >= 1 && sum2 >= 1 && sum3 >= 1 && sum4 >= 1 && sum5 >= 1) {
						vector<int> sum_of_area = { sum1, sum2, sum3, sum4, sum5 };
						sort(sum_of_area.begin(), sum_of_area.end());
						answer = min(answer, sum_of_area[4] - sum_of_area[0]);
					}

				}
			}
		}
	}
	cout << answer;
	return 0;
}