[백준][17779번] 게리맨더링2

www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

 

풀이과정

1. 완전탐색을 이용하여 모든 경우의 수를 구했다.

2. 기준점의 x, y를 정하고, d1, d2의 길이를 구하는 4중 포문을 만들었다.

3. 5번 구역의 경계선을 그리면 나머지 구역을 쉽게 구 할 수 있다.

4. 나머지 구역의 값이 정해지면 모든 구역의 총합에서 나머지 구역값을 빼면 5구역의 값이 된다.

 

*어떻게 접근 할 지 몰라 너무 오래걸린 문제였다.... 풀고보니 참 쉬웠다.....

 

소스코드(c++)

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int map[20][20];
int N;
int answer = 987654321;
int total = 0;
int dx[4] = {-1,1,1,-1};
int dy[4] = {1,1,-1,-1};
void solve(int x, int y, int d1, int d2) {
	
	//5area mask;
	int area[20][20] = { 0, };
	vector<pair<int, int>> point;
	vector<int> result(5, 0);
	point.push_back(make_pair(x - d1, y + d1));
	point.push_back(make_pair(x - d1 + d2, y + d1 + d2));
	point.push_back(make_pair(x + d2, y + d2));
	point.push_back(make_pair(x, y));
	int nx = x, ny = y;
	for (int i = 0; i < 4; i++) {
		while (1) {
			area[ny][nx] = 5;
			nx = nx + dx[i];
			ny = ny + dy[i];
			if (point[i].first == nx && point[i].second == ny) break;
		}
	}
	//1area mask;
	for (int i = 0; i < y + d1; i++) {
		for (int j = 0; j <= x; j++) {
			if (area[i][j] == 5) break;
			area[i][j] = 1;
			result[0] += map[i][j];
		}
	}
	//2area mask;
	for (int i = 0; i <= y + d2; i++) {
		for (int j = N - 1; j > x; j--) {
			if (area[i][j] == 5) break;
			area[i][j] = 2;
			result[1] += map[i][j];
		}
	}
	//3area mask
	for (int i = y + d1; i < N; i++) {
		for (int j = 0; j < x -d1 + d2; j++) {
			if (area[i][j] == 5) break;
			area[i][j] = 3;
			result[2] += map[i][j];
		}
	}
	//4area mask
	for (int i = y + d2 + 1; i < N; i++) {
		for (int j = N - 1; j >= x - d1 + d2; j--) {
			if (area[i][j] == 5) break;
			area[i][j] = 4;
			result[3] += map[i][j];
		}
	}
	result[4] = total;
	for (int i = 0; i < 4; i++) {
		result[4] -= result[i];
	}
	sort(result.begin(), result.end());
	int checkValue = result[4] - result[0];
	if (answer > checkValue) {
		answer = checkValue;
	}
}

void solution()
{
	for (int i = 0; i < N - 2; i++) {
		for (int j = 1; j < N - 1; j++) {
			for (int d1 = 1; d1 < N; d1++) {
				for (int d2 = 1; d2 < N; d2++) {
					if (j - d1 >= 0 && j + d2 < N &&
						i + d1 + d2 < N) {
						solve(j, i, d1, d2);
					}
				}
			}
		}
	}
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			total += map[i][j];
		}
	}
	solution();
	printf("%d\n", answer);
}

 

결과