[백준 17779번 게리맨더링2]
https://www.acmicpc.net/problem/17779
구현하는데 너무나 많이 애먹은 문제였다. 2일 정도를 고민하다 결국 다른 사람의 포스트를 참조하여 구현하였다. 예전 나의 코드는 예제는 다 통과하지만 채점과 동시에 계속 실패하였다(아직도 어떤 부분이 문제였는지 모르겠다).
풀이
1.
x, y, d1, d2의 범위를 부등식을 자세히 보면 구할 수 있다.
우선 1 ≤ x < x+d1+d2 ≤ N 이 식과 d1, d2 ≥ 1 이 식을 잘 보면, d1+d2의 최소값이 2이므로 1 <= x <= N-2의 범위를 구할 수 있다.
비슷하게 1 ≤ y-d1 < y < y+d2 ≤ N 이 식에서 2 <= y, y <= N-1을 구할 수 있다.
이 뿐만 아니라 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N 이 두 식을 d1, d2에 대하여 해석하면 d1, d2의 범위를 구할 수 있다.
d1, d2 >= 1이 주어져 있고, x+d1+d2 ≤ N이 식을 보면, d1, d2의 최소값이 각각 1이기 때문에 d1<=N-x-1, d2<=N-x-1이라는 두 가지 범위를 얻을 수 있다.
1 ≤ y-d1, y+d2 ≤ N 이 두 부등식을 통해서 d1<=y-1, d2<=N-y의 범위를 얻을 수 있다.
정리를 해보자면,
1 <= x <= N-2
2 <= y <= N-1
d1<=N-x-1, d1<=y-1
d2<=N-x-1, d2<=N-y
이렇게 네 가지의 범위를 얻을 수 있다.
2.
x,y,d1,d2의 범위를 모두 구했으니 5번 구역의 경계선의 (x,y)를 제외한 나머지 세 꼭지점이 지도 범위에 잘 포함되어 있는지 체크한다.
3.
체크가 끝났다면, 5번 경계선을 먼저 그려준다. 여기서 경계선 안에 포함되는 구역을 따로 칠하지 않을 것이다. 어차피 1,2,3,4번 구역을 정해주면서 각 구역의 인구 수를 구하고 총 인구 수에서 1~4번 구역 인구 수의 합을 빼주면 5번 구역 역시 구할 수 있기 때문이다.
4.
1~4번 구역을 지도의 각 모서리부터 안쪽으로 들어오면서 칠해주고, 도중에 5번 구역을 만나고 break를 통해 for문을 빠져나온다. 구역을 칠해주면서 해당 구역의 인구 수를 더해주는 것도 잊지말자.
5.
1~4번 구역을 모두 칠하고 각 구역의 인구 수의 합도 구했다면, 총 인구 수에서 네 구역 인구 수의 합을 빼서 5번 구역의 인구 수를 구해준다.
1~5번 구역 인구 수를 인구 수 순서대로 정렬하고 가장 많은 구역의 인구 수에서 가장 적은 구역의 인구 수를 빼준다.
6.
ans = min(ans, mx-mn) 를 통해 인구 수의 차가 가장 적게 나는 경우를 찾는다.
C++ 코드
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility> // pair
#include <tuple>
#include <stack>
// #include <map>
#include <unordered_map>
#define ll long long
#define INF 1e9
using namespace std;
int ans = INF;
int r,c;
int A[21][21];
int map[21][21];
int pop[6] = {0,};
int total;
int n;
void district(int x, int y, int d1, int d2) {
// border of 5
for(int i=0;i<=d1;++i) {
map[x+i][y-i] = 5;
map[x+d2+i][y+d2-i] = 5;
}
for(int i=1;i<=d2;++i) {
map[x+i][y+i] = 5;
map[x+d1+i][y-d1+i] = 5;
}
// 1
for(int i=1;i<x+d1;++i) {
for(int j=1;j<=y;++j) {
if(map[i][j] == 5) break;
map[i][j] = 1;
pop[1] += A[i][j];
}
}
// 2
for(int i=1;i<=x+d2;++i) {
for(int j=n;j>=y+1;--j) {
if(map[i][j] == 5) break;
map[i][j] = 2;
pop[2] += A[i][j];
}
}
// 3
for(int i=n;i>=x+d1;--i) {
for(int j=1;j<y-d1+d2;++j) {
if(map[i][j] == 5) break;
map[i][j] = 3;
pop[3] += A[i][j];
}
}
// 4
for(int i=n;i>x+d2;--i) {
for(int j=n;j>=y-d1+d2;--j) {
if(map[i][j] == 5) break;
map[i][j] = 4;
pop[4] += A[i][j];
}
}
}
bool check(int x, int y, int d1, int d2) {
if (x + d1 > n || y - d1 < 1) return false;
if (x + d2 > n || y + d2 > n) return false;
if (x + d1 + d2 > n || y - d1 + d2 > n) return false;
return true;
}
void sol() {
for(int i=1;i<=n-2;++i) {
for(int j=2;j<=n-1;++j) {
for(int d1=1;d1<=n-i-1 && d1<=j-1;++d1) {
for(int d2=1;d2<=n-i-1 && d2<=n-j;++d2) {
if(check(i,j,d1,d2)) {
memset(map, 0, sizeof(map));
memset(pop, 0, sizeof(pop));
district(i,j,d1,d2);
pop[5] = total - (pop[1]+pop[2]+pop[3]+pop[4]);
sort(pop+1, pop+6);
ans = min(ans, pop[5]-pop[1]);
}
}
}
}
}
return;
}
int main(void) {
// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
scanf("%d", &n);
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
scanf("%d", &A[i][j]);
total += A[i][j];
}
}
sol();
printf("%d\n", ans);
return 0;
}실행 결과
