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

statco19·2022년 1월 31일
0

알고리즘연습

목록 보기
19/27

[백준 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;
}

실행 결과

profile
조금씩 나아지는 중입니다!

0개의 댓글