BOJ ::17779 게리맨더링 2

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

17779번: 게리맨더링 2

 

브루트 포스 문제.

가능한 선거구를 모두 찾아서 그것의 (최대-최소)의 최솟값을 계산해주어야 한다.

5번 선거구가 있는 사각형 선거구를 그리는 것이 좀 복잡하다.

1~4번 선거구는 문제에 친절하게 나와있으므로 그대로 구현.

또한, check 함수를 이용해서 d1, d2를 활용하였을 때 선거구를 만들 수 있는 좌표인가를 확인해주어야 한다. 

 

 

다른 분 풀이를 살펴보다가

max_element, min_element라는 함수를 새롭게 알았다. 

원하는 인덱스 구간만큼 최대 최소를 알아서 찾아주는 함수이다.

주의할 것은 주소형태로 반환되므로 포인터를 사용해서 값을 얻어야 한다.

 

 

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

int N, area[22][22], temp[22][22];
int ans = 1e+9;
bool check(int r, int c, int d1, int d2) {	//경계선 안에 있는가 
	if (r + d1 > N || r + d2 > N) return false;
	if (r + d1 + d2 > N) return false;
	if (c - d1 <= 0 || c + d2 > N) return false;
	if (c - d1 + d2 <= 0 || c - d1 + d2 > N) return false;
	return true;
	
}
int draw(int r, int c, int d1, int d2) {
	memset(temp, 0, sizeof(temp));
	bool change = false;
	int t1 = 0, t2 = 0; 
	bool flag1 = false, flag2 = false;		//전환

	//5번구역 - 사각형 구역
	for (int x = r; x <= r + d1 + d2; x++) {
		for (int y = c - t1; y <= c + t2; y++) {
			temp[x][y] = 5;
		}

		if (!flag1) ++t1;
		else --t1;

		if (!flag2) ++t2;
		else --t2;

		if (t1 == d1) flag1 = true;
		if (t2 == d2) flag2 = true;
	}
	//1~4번 구역
	for (int x = 1; x <= N; x++) {
		for (int y = 1; y <= N; y++) {
			if (temp[x][y] == 5) continue;
			if (1 <= x && x < r + d1 && 1 <= y && y <= c) temp[x][y] = 1;
			else if (1 <= x && x <= r + d2 && c < y && y <= N) temp[x][y] = 2;
			else if (r + d1 <= x && x <= N && 1 <= y && y < c - d1 + d2) temp[x][y] = 3;
			else if (r + d2 < x && x <= N && c - d1 + d2 <= y && y <= N) temp[x][y] = 4;

		}
	}
	vector <int> v;
	v.assign(6, 0); // 1~5까지 사용할 거니까 6개에 0 할당
	int Max = 0, Min = 1e+9;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			v[temp[i][j]] += area[i][j];
		}
	}
	//인덱스 0 인것은 제외하고 최대최소 인구 찾기
	Max = *max_element(v.begin() + 1, v.end());
	Min = *min_element(v.begin() + 1, v.end());

	return Max - Min;
}
void do_case(int r, int c) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (check(r, c, i, j)) {
				int tm = draw(r, c, i, j);
				ans = min(ans, tm);
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> area[i][j];
		}
	}

	//구역을 만들 수 있는 가능한 모든 점에 대해서
	for (int i = 0; i <= N - 2; i++) {
		for (int j = 2; j <= N - 1; j++) {
			do_case(i, j);
		}
	}
	cout << ans << "\n";
	return 0;
}