[삼성] 게리멘더링2

문제 요약

환경

• n*n 크기의 땅이 있습니다.
• 5개의 지역구로 나누어야합니다.
• 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

지역구를 나누는 규칙

선거구를 나누는 방법은 다음과 같다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.
   (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
   1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
   2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
   3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
   4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

아이디어

더러운 스타트택시 같은 문제는 나오지 않고 이런 문제나 나왔으면^^^..

정말 순수하게 문제에 적힌 조건들을 복붙하다시피 완전탐색을 해줬다.
특히 상수시간에 x y d1 d2에 관한 조건을 검사하면 모든 경우를 얻어낼 수 있어서 매우 마음이 편했다.

양심리스지만 편했던 x y d1 d2 검사

x y의 경우 가능한 범위 안에서 탐색을 해서 굳이 검사를 안 해도 되는 조건도 껴 있지만 그냥 문제에서 준 부등호들을 싹다 긁어모았다..

// (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
bool valid_setting(int x, int y, int d1, int d2) {
	return d1 >= 1 && d2 >= 1 && 1 <= x && x < x + d1 + d2 && x + d1 + d2 <= n && 1 <= y - d1 && y - d1 < y&& y + d2 <= n;
}

다이아몬드 모양의 안쪽을 채우기

다양한 방법이 있겠지만, 나는 각 행에서 5영역이 시작되는 열과 끝나는 열을 찾아 그 안을 채워주었다

for (int r = 1; r <= n; r++) {
	//starting end잡기
	bool on = false;
	int sc =-1, ec=-1;
	for (int c = 1; c <= n; c++) {
		if (!on&&part[r][c] == 5) {
			sc = c; ec = c; on = true;
		}
		if (on && part[r][c] == 5) {
			ec = c;
		}
	}
	if (sc != -1) {
		for (int c = sc; c <= ec; c++) {
			part[r][c] = 5;
		}
	}
}

코드

#include<iostream>
#include<memory.h>
#include<math.h>
using namespace std;
int n;
int map[21][21];
int part[21][21];//5거나 0이면 5구역
int res = 20 * 20* 100;
// (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
bool valid_setting(int x, int y, int d1, int d2) {
	return d1 >= 1 && d2 >= 1 && 1 <= x && x < x + d1 + d2 && x + d1 + d2 <= n && 1 <= y - d1 && y - d1 < y&& y + d2 <= n;
}
/*
void print_part() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << part[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
*/
//x는 세로 y는 가로
void draw(int x, int y, int d1, int d2) {
	memset(part, 0, sizeof(part));
	for (int i = 0; i <= d1; i++) {
		part[x + i][y - i] = 5;
		part[x + d2 + i][y + d2 - i] = 5;
	}
	for (int i = 0; i <= d2; i++) {
		part[x + i][y + i] = 5;
		part[x +d1+ i][y -d1+ i] = 5;
	}

	int n_fives = 0;
for (int r = 1; r <= n; r++) {
	//starting end잡기
	bool on = false;
	int sc =-1, ec=-1;
	for (int c = 1; c <= n; c++) {
		if (!on&&part[r][c] == 5) {
			sc = c; ec = c; on = true;
		}
		if (on && part[r][c] == 5) {
			ec = c;
		}
	}
	if (sc != -1) {
		for (int c = sc; c <= ec; c++) {
			part[r][c] = 5;
		}
	}
}
	//1번 선거구
	for (int r = 1; r < x + d1; r++) {
		for (int c = 1; c <= y; c++) {
			if(part[r][c] == 0)
				part[r][c] = 1;
		}
	}
	//2번
	for (int r = 1; r <= x + d2; r++) {
		for (int c = y + 1; c <= n; c++) {
			if (part[r][c] == 0)
				part[r][c] = 2;
		}
	}
	for (int r = x + d1; r <= n; r++) {
		for (int c = 1; c < y - d1 + d2; c++) {
			if (part[r][c] == 0)
				part[r][c] = 3;
		}
	}
	for (int r = x + d2 + 1; r <= n; r++) {
		for (int c = y - d1 + d2; c <= n; c++) {
			if (part[r][c] == 0)
				part[r][c] = 4;
		}
	}
	//print_part();
	int people[6] = { 0, };
	for (int r = 1; r <= n; r++) {
		for (int c = 1; c <= n; c++) {
			people[part[r][c]] += map[r][c];
		}
	}
	int max_people = 0, min_people = 20 * 20 * 100;
	for (int i = 1; i <= 5; i++) {
		//cout << "sum_" << i << " : " << people[i] << endl;
		max_people = max(max_people, people[i]);
		min_people = min(min_people, people[i]);
	}
	//cout << "max - min : " << max_people - min_people << endl;
	res = min(res, max_people - min_people);
	//cout << "cur res : " << res << endl;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	
	for (int x = 1; x <= n-2; x++) {
		for (int y = 1; y <= n - 1; y++) {
			for (int d1 = 1; d1 < n; d1++) {
				for (int d2 = 1; d2 < n; d2++) {
					if (valid_setting(x, y, d1, d2)) {
						draw(x, y, d1, d2);
					}
					
				}
			}
		}
	}
	cout<< res << endl;

}