[C++] 게리맨더링2 (17779번)

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

17779번: 게리맨더링 2

---

문제풀이

개인적으로 상성이 너무 안맞는 문제다. 2차원 배열의 인덱스를 잘 조절하여 만복문을 돌리는건데 덧셈 뺄셈이 너무 헷갈려 죽는줄 알았다.

 

조건을 보면 사각형 모양의 테두리는 반드시 생겨야 한다.

시작지점 행 열을 0으로 두고 풀었다.

 

그러므로 열의 시작지점은 반드시 1부터 n-2 사이 이어야 한다.

행의 시작지점은 0부터 n-3까지 이어야 한다. 그래야 사각형이 만들어진다.

그리고 d1은 현재 열 인덱스 값보다 작거나 같아야 하고, d2는 n-현재열보다 작거나 같아야 한다. 그래야 양 끝이 배열을 넘지 않는다. 그리고 d1+d2+현재행의 값이 n보다 크면 안된다.

이 조건을 만족하는 모든 값들을 반복문 돌리면 된다.

난 1, 2, 3, 4 구역을 구하고 5구역은 총합에서 네 구역 값을 빼는 방식으로 구했다.

 

모두 행을 기준으로 반복을 돌도록 하였다.

현재 행을 i, 열을 j라고 한다.

1구역의 행은 0~i+d1이다. 1구역의 열은 상황에 따라 다른데, i>r이면 열은 0~j까지다. 그게 아니라면, 행을 내려가며 열 계산하는 부분을 1씩 빼주면 된다.

말로하니 굉장히 어려운데 실제로도 계산하는데 머리 터지는줄 알았다. 이런 방법으로 4구역을 모두 계산해 값을 정리하면 된다. 이거 계산하는게 정말 .... 쉽지않다.

 

#include <iostream>

using namespace std;

int n;
int arr[100][100];

int main() {
    cin >> n;
    int sum = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> arr[i][j];
            sum += arr[i][j];
        }
    }

    int answer = 999999999;

    for(int i=0; i<n-2; i++) {
        for(int j=1; j<n-1; j++) {
            for(int d1=1; j-d1>=0; d1++) {
                for(int d2=1; n-j-d2>0; d2++) {
                    if(n-(i+d1+d2)<=0) continue;
                    int min_value = 999999999;
                    int max_value = 0;
                    int arr5 = sum;
                    // cout << i << " " << j << endl;

                    // 1구역
                    int cnt = 0;
                    for(int r=0; r<i+d1; r++) {
                        int tmp;
                        if(i>r) tmp = 0;
                        else tmp = r-i+1;
                        // cout << "aa " << r << " " << tmp << endl;
                        for(int c=0; c<=j-tmp; c++) {
                            cnt += arr[r][c];
                        }
                    }
                    min_value = min(min_value, cnt);
                    max_value = max(max_value, cnt);
                    arr5 -= cnt;
                    // cout << cnt << " ";

                    // 2구역
                    cnt = 0;
                    for(int r=0; r<=i+d2; r++) {
                        int tmp;
                        if(i>=r) tmp = 0;
                        else tmp = r-i;
                        // cout << "aa " << i << " " << r << " " << tmp << endl;
                        for(int c=j+1+tmp; c<n; c++) {
                            cnt += arr[r][c];
                        }
                    }
                    min_value = min(min_value, cnt);
                    max_value = max(max_value, cnt);
                    arr5 -= cnt;
                    // cout << cnt << " ";

                    // 3구역
                    cnt = 0;
                    for(int r=i+d1; r<n; r++) {
                        int tmp;
                        if(r>=i+d1+d2) tmp = d2;
                        else tmp = r-(i+d1);
                        for(int c=0; c<j-d1+tmp; c++) {
                            cnt += arr[r][c];
                        }
                    }
                    min_value = min(min_value, cnt);
                    max_value = max(max_value, cnt);
                    arr5 -= cnt;
                    // cout << cnt << " ";

                    // 4구역
                    cnt = 0;
                    for(int r=i+d2+1; r<n; r++) {
                        int tmp;
                        if(r>i+d1+d2) tmp = d1;
                        else tmp = r-(i+d2+1);
                        // cout << "aa " << i << " " << r << " " << tmp << endl;
                        for(int c=j+d2-tmp; c<n; c++) {
                            cnt += arr[r][c];
                        }
                    }
                    min_value = min(min_value, cnt);
                    max_value = max(max_value, cnt);
                    arr5 -= cnt;
                    // cout << cnt << " ";

                    // 5구역
                    min_value = min(min_value, arr5);
                    max_value = max(max_value, arr5);
                    // cout << arr5 << endl;

                    answer = min(answer, max_value-min_value);

                    // return 0;
                }
            }
        }
    }
    cout << answer;
    return 0;
}