[Baekjoon] 17779번 게리맨더링 2 (Java) 문제 풀이 [Gold 3]

문제

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

17779번: 게리맨더링 2

 

어떻게 풀 것인가?

사실 문제 자체가 길고, 너무 난해해서 어려웠던 문제 하지만, 문제를 이해하고 시키는 조건들을 코드로 바꾼다면 그리 어려운 알고리즘은 없는 그런 문제였다.

 

즉, 정말 빡센 브루트포스 + 구현 문제였다.

경계선을 구하기 위해서 단지 모든 경우의 수를 계산해야하만 한다.

즉, X,Y,D1,D2 모두를 4중 For문을 통해서 계속해서 경우의 수 모두를 검증하고 답을 찾는 문제였다.

 

그렇다면 이러한 비효율적인? 4중 For문이 되는 이유는 무엇일까?

N의 조건을 살펴보자.

• 5 ≤ N ≤ 20

즉 최대 N은 20이다.

 

단순 계산으로 N의 경우가 20까지 임으로 시간복잡도는 20*20*20*20 = 160000이다.

 

하지만 문제의 시간제한은 1초 즉 = 1억번이다.

 

그렇기에 이 문제를 풀 때는 브루트포스가 가능하다.

 

 

풀면서 놓쳤던점

문제를 처음에 이해하는 것이 오래 걸렸다.

 

이 문제를 통해 얻어갈 것

빡센 구현 연습

 

내 코드 

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

class Main {
    static int N;
    static int[][] arr;
    static int totalPeople = 0;
    static int min = Integer.MAX_VALUE;

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

        // input
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        arr = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                totalPeople += arr[i][j];
            }
        }

        // solution
        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;

                        simulation(x, y, d1, d2);
                    }
                }
            }
        }

        System.out.println(min);
    }

    static void simulation(int x, int y, int d1, int d2) {
        boolean[][] border = new boolean[N][N];

        for (int i = 0; i <= d1; i++) {
            border[x + i][y - i] = true;
            border[x + d2 + i][y + d2 - i] = true;
        }

        for (int i = 0; i <= d2; i++) {
            border[x + i][y + i] = true;
            border[x + d1 + i][y - d1 + i] = true;
        }

        int[] peopleSum = new int[5];

        for (int i = 0; i < x + d1; i++) {
            for (int j = 0; j <= y; j++) {
                if (border[i][j]) break;
                peopleSum[0] += arr[i][j];
            }
        }

        for (int i = 0; i <= x + d2; i++) {
            for (int j = N - 1; j > y; j--) {
                if (border[i][j]) break;
                peopleSum[1] += arr[i][j];
            }
        }

        for (int i = x + d1; i < N; i++) {
            for (int j = 0; j < y - d1 + d2; j++) {
                if (border[i][j]) break;
                peopleSum[2] += arr[i][j];
            }
        }

        for (int i = x + d2 + 1; i < N; i++) {
            for (int j = N - 1; j >= y - d1 + d2; j--) {
                if (border[i][j]) break;
                peopleSum[3] += arr[i][j];
            }
        }

        peopleSum[4] = totalPeople;

        for (int i = 0; i < 4; i++) {
            peopleSum[4] -= peopleSum[i];
        }

        Arrays.sort(peopleSum);

        min = Math.min(min, peopleSum[4] - peopleSum[0]);
    }
}

 

참고

X