[BOJ] 17779 게리멘더링 2

 

 

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static int n,result,total = 0;
	static int[][] map;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				total += map[i][j];
			}
		}
		result = Integer.MAX_VALUE;
		for(int x=0;x<n;x++) {
			for(int y=0;y<n;y++) {
				for(int d1=1;d1<n;d1++) {
					for(int d2=1;d2<n;d2++) {
						if(x+d1+d2>=n) continue;
						if(y-d1<0 || y+d2>=n) continue;
						cal(x,y,d1,d2);
					}
				}
			}
		}
		System.out.println(result);
	}
	private static void cal(int x,int y,int d1,int d2) {
		boolean[][] edge = new boolean[n][n];
		for(int i=0;i<=d1;i++) {
			edge[x+i][y-i] = true;
			edge[x+d2+i][y+d2-i] = true;
		}
		for(int i=0;i<=d2;i++) {
			edge[x+i][y+i] = true;
			edge[x+d1+i][y-d1+i] = true;
		}
		int[] people = new int[5];
		for(int i=0;i<x+d1;i++) {
			for(int j=0;j<=y;j++) {
				if(edge[i][j]) break;
				people[0] += map[i][j];
			}
		}
		for(int i=0;i<=x+d2;i++) {
			for(int j=n-1;j>y;j--) {
				if(edge[i][j]) break;
				people[1] += map[i][j];
			}
		}
		for(int i=x+d1;i<n;i++) {
			for(int j=0;j<y-d1+d2;j++) {
				if(edge[i][j]) break;
				people[2] += map[i][j];
			}
		}
		for(int i=x+d2+1;i<n;i++) {
			for(int j=n-1;j>=y-d1+d2;j--) {
				if(edge[i][j]) break;
				people[3] += map[i][j];
			}
		}
		int totalSum = total;
		for(int i=0;i<4;i++) {
			totalSum -= people[i];
		}
		people[4] = totalSum;
		Arrays.sort(people);
		result = Math.min(result, people[4] - people[0]);
	}
}