문제 요약
환경
- n*n 크기의 땅이 있습니다.
- 5개의 지역구로 나누어야합니다.
- 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.
지역구를 나누는 규칙
선거구를 나누는 방법은 다음과 같다.
- 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
- 다음 칸은 경계선이다.
(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) - 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
- 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;
}