BAEK_17779_게리맨더링2

11월 13일 in Category / Algorithm

BAEKJOON

17779. 게리맨더링2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, A[][], MIN, MAX, GAP, SUM;

	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine().trim());

		A = new int[N + 2][N + 2];
		SUM = 0;
		GAP = Integer.MAX_VALUE;

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 1; j <= N; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
				SUM += A[i][j];
			}
		}

		for (int i = 2; i <= N - 3; i++) {
			for (int j = 3; j <= N - 2; j++) {
				loops: for (int k = 1;1 < j - k ; k++) {
					for (int l = 1;j + l < N; l++) {
						if ((i + k + l) < N) {
							getGAP(i, j, k, l);
						}
//						else {
//							break loops;
//						}
					}
				}
			}
		}
//		getGAP(3, 5, 2, 1);
		System.out.println(GAP);
	}

	private static void getGAP(int x, int y, int d1, int d2) {
		int sum = 0, five = SUM;
		MIN = Integer.MAX_VALUE;
		MAX = Integer.MIN_VALUE;
		
		// 1번 구역
		sum = 0;

		for (int i = 1; i < x; i++) {
			for (int j = 1; j <= y; j++) {
				sum += A[i][j];
			}
		}

		for (int i = x, k = 1; i < x + d1; i++, k++) {
			for (int j = 1; j <= y - k; j++) {
				sum += A[i][j];
			}
		}
		five -= sum;
		MIN = Math.min(MIN, sum);
		MAX = Math.max(MAX, sum);
		
		
		// 2번 구역
		sum = 0;

		for(int j=N; j>y+d2; j--) {
			for (int i = 1; i <= x + d2; i++) {
				sum += A[i][j];
			}			
		}
		for (int j = y+d2, k = 1; j > y; j--, k++) {
			for (int i = 1; i <= x + d2 - k; i++) {
				sum += A[i][j];
			}
		}
		five -= sum;
		MIN = Math.min(MIN, sum);
		MAX = Math.max(MAX, sum);
		
		// 3번 구역
		sum = 0;
		
		for(int j=1; j<y-d1; j++) {
			for (int i = x + d1; i <= N; i++) {
				sum += A[i][j];
			}
		}
		
		for (int j = y-d1, k = 1; j < y - d1 + d2; j++, k++) {
			for (int i = x + d1 + k; i <= N; i++) {
				sum += A[i][j];
			}
		}
		five -= sum;
		MIN = Math.min(MIN, sum);
		MAX = Math.max(MAX, sum);

		// 4번 구역
		sum = 0;
		
		for(int i=N; i>x+d1+d2; i--) {
			for(int j=y-d1+d2; j<=N; j++) {
				sum+=A[i][j];
			}
		}
		for(int i=x+d1+d2, k=1; i>x+d2; i--, k++) {
			for(int j=y-d1+d2+k; j<=N; j++) {
				sum+=A[i][j];
			}
		}
		five -= sum;
		MIN = Math.min(MIN, sum);
		MAX = Math.max(MAX, sum);

		// 5번 구역
		MIN = Math.min(MIN, five);
		MAX = Math.max(MAX, five);

		GAP = Math.min(GAP, MAX - MIN);

	}
}