[백준] 17779 게리맨더링2 (Java)

[17779 게리맨더링2]

난이도: 골드4

17779번: 게리맨더링 2

문제

입력

출력

---

[아이디어]

가능한 모든 경우들을 완탐으로 풀었다.

 

1, 2, 3, 4번 선거구역을 나눠주고 해당되지 않는 구역을 5번 구역으로 판단해서 값을 구해줬다.

여기서 선거구역을 나눌 때 경계선의 꼭지점들을 기준으로 판단해주었다.

 

예를 들면, x = 4, y = 3, d1 = 1, d2 = 1 의 경우

1번 선거구역을 찾기 위해 (x, y) => (4, 3) 을 기준으로 위에 있는 칸들을 먼저 찾아주고

r이 3이하인 경우에는 가로의 길이를 하나씩 줄여서 (x + d1, y-d1) => (5, 2) 위까지 찾아주었다.

위의 설명을 코드로 구현하면 아래와 같다.

for(int r = 1, C = y; r < x + d1; r++) {
    if(r >= x) {
        C--;
    }
    for(int c = 1; c <= C; c++) {
        sum += A[r][c];
    }
}

2번 선거 구역은 (x + d2, y + d2) => (5, 4) 를 기준으로 오른쪽에 있는 칸들을 먼저 찾아주고

c가 4이하인 경우에는 높이를 하나씩 줄여서 (x, y) => (4, 3) 오른쪽까지 찾아주었다.

위의 설명을 코드로 구현하면 아래와 같다.

for(int c = N, R = x + d2; c > y; c--) {
    if(c <= y + d2) {
        R--;
    }
    for(int r = 1; r <= R; r++) {
        sum += A[r][c];
    }
}

이런 방식으로 3, 4번 구역도 찾아주었다.

 

그 다음엔 문제에 나와있듯이 가장 많은 인구수에서 가장 적은 인구수를 뺀 최솟값을 찾아주었다.

---

[JAVA 코드]

import java.io.*;
import java.util.*;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	static int N, total, minDiff = Integer.MAX_VALUE;
	static int [][] A;

	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine());
		A = new int [N + 1][N + 1];
		for(int r = 1; r <= N; r++) {
			tokens = new StringTokenizer(br.readLine());
			for(int c = 1; c <= N; c++) {
				A[r][c] = Integer.parseInt(tokens.nextToken());
				total += A[r][c];
			}
		}
		
		for(int x = 1; x <= N; x++) {
			for(int y = 1; y <= N; y++) {
				for(int d1 = 1; ; d1++) {
					if(y - d1 < 1) break;
					for(int d2 = 1; ; d2++) {
						if(x + d1 + d2 > N || y + d2 > N) break;
						calcSub(x, y, d1, d2);
					}
				}
			}
		}
		
		System.out.println(minDiff);
	}

	private static void calcSub(int x, int y, int d1, int d2) {
		int max = -1;
		int min = Integer.MAX_VALUE;
		int area5 = total;
		
		// 1번 선거구역
		int sum = 0;
		for(int r = 1, C = y; r < x + d1; r++) {
			if(r >= x) {
				C--;
			}
			for(int c = 1; c <= C; c++) {
				sum += A[r][c];
			}
		}
		max = Math.max(max, sum);
		min = Math.min(min, sum);
		area5 -= sum;
		
		// 2번 선거구역
		sum = 0;
		for(int c = N, R = x + d2; c > y; c--) {
			if(c <= y + d2) {
				R--;
			}
			for(int r = 1; r <= R; r++) {
				sum += A[r][c];
			}
		}
		max = Math.max(max, sum);
		min = Math.min(min, sum);
		area5 -= sum;
		
		// 3번 선거구역
		sum = 0;
		for(int c = 1, R = x + d1; c < y - d1 + d2; c++) {
			if(c >= y - d1) {
				R++;
			}
			for(int r = R; r <= N; r++) {
				sum += A[r][c];
			}
		}
		max = Math.max(max, sum);
		min = Math.min(min, sum);
		area5 -= sum;
		
		// 4번 선거구역
		sum = 0;
		for(int r = N, C = y - d1 + d2; r > x + d2; r--) {
			if(r <= x + d1 + d2) {
				C++;
			}
			for(int c = C; c <= N; c++) {
				sum += A[r][c];
			}
		}
		max = Math.max(max, sum);
		min = Math.min(min, sum);
		area5 -= sum;
		
		// 5번 선거구역
		max = Math.max(max, area5);
		min = Math.min(min, area5);
		
		minDiff = Math.min(minDiff, max - min);
		
	}

}