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

https://www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

 

기준점 (x,y)와 경계 길이인 d1,d2에 따라 5개 구역으로 나누어 인구가 가장 많은 구역과 작은 구역의 차이의 최솟값을 구하는 문제이다.

 

먼저 기준점 (x,y)가 (1,1)부터 (N,N)까지 모두 돌아야겠다는 생각이 들었다. -> 브루트포스

그 다음 경계선의 길이인 d1과 d2는 문제에서 주어진 조건에 따르면 경계선의 사각형의 4꼭짓점이 NXN에 포함되야 하므로 이를 통해d1은 범위가 정해지는 반면 d2는 오른쪽 꼭짓점의 y좌표의 범위인 y+d2<=N 과 아래 꼭짓점의 x좌표의 범위인 x+d1+d2<=N 둘 다 만족해야하므로 범위가 정해지지 않는다. 따라서 일단 d2의 범위는 1부터 N까지해서 따로 위 두 조건을 만족하는지 검사하였다.

 

여기까지 기준점과 d1,d2를 조건을 만족하면서 모두 돌 수 있도록 범위를 정하였다.이후 기준점과 d1,d2에 따른 경계선으로 나눠진 5개의 구역 중 (r,c)가 몇 번 구역에 속하는지 저장해줘야한다. 이것은 먼저 구역을 저장하는 2차원 배열을 모두 5로 초기화해서 문제에서 주어진 구역 조건에 따라 몇 번 구역에 속하는지 저장해주었다.

 

여기까지 기준점이 (x,y)이고 경계선의 길이가 d1, d2일 때의 선거구를 나눠줬기에 인구수 합의 차이값을 구해주며 차이값의 최솟값을 구하면 된다.

 

#include <iostream>

using namespace std;

int A[22][22]; // 칸 인구 수 
int B[22][22]; // 선거구
int N, resultMin=9999;

int check(int x, int y, int d1, int d2) {
	if(d2 > N-d1-x || d2 > N-y) return 1;
	else return 0;
}

void popu(int x, int y, int d1, int d2) {
	int SUM[6] = {0, }; // 각 선거구 인구수 합 초기화 
	// 각 선거구 초기화 
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=N; j++) {
			B[i][j] = 5;
		}
	}
	// 1번 선거구 
	int cnt=0;
	for(int r=1; r<x+d1; r++) {
		if(r>=x) cnt++;
		for(int c=y-cnt; c>=1; c--) {
			B[r][c] = 1;
		}
	}
	// 2번 선거구
	cnt=0;
	for(int r=1; r<=x+d2; r++) {
		if(r>x) cnt++;
		for(int c=y+1+cnt; c<=N; c++) {
			B[r][c] = 2;
		}
	} 
	// 3번 선거구
	cnt=0;
	for(int r=N; r>=x+d1; r--) {
		if(r<x+d1+d2) cnt++;
		for(int c=y+d2-d1-1-cnt; c>=1; c--) {
			B[r][c] = 3;
		}
	}
	// 4번 선거구
	cnt=0;
	for(int r=N; r>x+d2; r--) {
		if(r<=x+d1+d2) cnt++;
		for(int c=y+d2-d1+cnt; c<=N; c++) {
			B[r][c] = 4;
		}
	}
	// 각 선거구 인구수 합
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=N; j++) {
			SUM[B[i][j]] += A[i][j];
		}
	}
	// 가장 많은 선거구와 적은 선거구
	int max=0, min=9999;
	for(int i=1; i<=5; i++) {
		if(SUM[i] > max) max = SUM[i];
		if(SUM[i] < min) min = SUM[i];
	}
	// 차이 값
	int result = max - min;
	if(resultMin > result) resultMin = result;
}

int main(void) {
	cin >> N;
	
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=N; j++) {
			cin >> A[i][j];
			B[i][j] = 5;
		}
	}
	
	for(int x=1; x<=N; x++) {
		for(int y=1; y<=N; y++) {
			for(int d1=1; d1<=y-1; d1++) {
				for(int d2=1; d2<=N; d2++) {
					if(!check(x,y,d1,d2)) {
						popu(x,y,d1,d2);
					}
				}
			} 
		}
	}
	
	cout << resultMin;
}

 

 

떠오르기 힘들었던 로직은

(r,c)가 몇 번 선거구인지 판별할 때 계단식으로 줄어드는 구역을 cnt변수를 통해 범위를 동적으로 줄여주며 저장해주는 것과

몇 번 선거구인지 저장하는 배열을 선거구의 인구수 합을 저장하는 배열의 인덱싱으로 사용하는 것이었다.