import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; // BOJ 17779번 게리멘더링 2 public class Main { static int n; static int[][] population; static int minDiff = Integer.MAX_VALUE; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); population = new int[n + 1][n + 1]; for (int i = 1; i <= n; i++) { String[] nums = br.readLine().split(" "); for (int j = 1; j <= n; j++) { population[i][j] = Integer.parseInt(nums[j-1]); } } // 선거구를 확정하고 인구 차이를 계산하는 메서드 solution(); System.out.println(minDiff); } private static void solution() { // d1으로 가능한 모든 경우의 수에 대해 탐색 for (int d1 = 1; d1 <= n - 2; d1++) { // d2의 가능한 모든 경우의 수에 대해 탐색 for (int d2 = 1; d2 <= n - d1 - 1; d2++) { // d1, d2가 정해짐에 따라 x의 범위 fix for (int x = 1; x <= n - d1 - d2; x++){ // d1, d2가 정해짐에 따라 y의 범위 fix for (int y = d1 + 1; y <= n - d2; y++) { calcPopulation(x, y, d1, d2); } } } } } private static void calcPopulation(int x, int y, int d1, int d2) { int[][] map = new int[n + 1][n + 1]; // 1번, 4번 경계선 그리기 for (int i = 0; i <= d1; i++){ map[x + i][y - i] = 5; map[x + d2 + i][y + d2 - i] = 5; } // 2번, 3번 경계선 그리기 for (int i = 0; i <= d2; i++){ map[x + i][y + i] = 5; map[x + d1 + i][y - d1 + i] = 5; } // 5번 선거구 내부 채우기 - 경계선이 한 줄에 하나만 있어도 커버 가능 for (int r = 1; r <= n; r++) { boolean isInside = false; for (int c = 1; c <= n; c++) { if (map[r][c] == 5) { isInside = !isInside; // 경계선 만날 때마다 안/밖 토글 } else if (isInside) { map[r][c] = 5; // 경계선 내부면 5번으로 채움 } } } // 나머지 선거구 배정 for (int r = 1; r <= n; r++){ for (int c = 1; c <= n; c++){ // 아직 할당되지 않은 구역이라면, if (map[r][c] == 0){ // 1번 선거구 if (r < x + d1 && c <= y){ map[r][c] = 1; // 2번 선거구 } else if (r <= x + d2 && y < c) { map[r][c] = 2; // 3번 선거구 } else if (x + d1 <= r && c < y - d1 + d2){ map[r][c] = 3; // 4번 선거구 } else if (x + d2 <= r && y - d1 + d2 <= c) { map[r][c] = 4; } } } } // 각 선거구 별 인구 수 계산 int[] regionPopulation = new int[6]; for (int r = 1; r <= n; r++){ for (int c = 1; c <= n; c++){ // k번 선거구에 그 칸의 인구수 누적 regionPopulation[map[r][c]] += population[r][c]; } } // 초기값 지정 int maxPopulation = 0; int minPopulation = Integer.MAX_VALUE; // 최대, 최소 반복마다 갱신 for (int i = 1; i<= 5; i++) { maxPopulation = Math.max(maxPopulation, regionPopulation[i]); minPopulation = Math.min(minPopulation, regionPopulation[i]); } // 이전 회차에서 구한 최솟값과 이번 회차에서의 인구수 차를 비교하여 갱신 minDiff = Math.min(minDiff, maxPopulation - minPopulation); } }

제출 #168646

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: