백준 17779번 : 게리맨더링 2 - brute Force cpp

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

17779번: 게리맨더링 2

1. 문제설명

 

 

 

 

 

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;


int N, population[21][21], group[21][21]; //인구수
int ans = INT_MAX;
int x, y, d1, d2;


void Input();

int getMinDifference();

void groupMarking() {
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            if (r < x + d1 && c <= y) group[r][c] = 1;
            else if (r <= x + d2 && c > y && c <= N) group[r][c] = 2;
            else if (r >= x + d1 && r <= N && c >= 1 && c < y - d1 + d2) group[r][c] = 3;
            else if (x + d2 < r && y - d1 + d2 <= c) group[r][c] = 4;
        }
    }


    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            if (r + c >= x + y && r + c <= x + y + 2 * d2 && r >= c + x - y && r <= c + x - y + 2 * d1) group[r][c] = 5;
        }
    }

}

//x,y, d1, d2 결정
void divideGroup() {
    for (x = 1; x <= N; x++) {
        for (y = 1; y <= N; y++) {
            for (d1 = 1; d1 <= N; d1++) {
                for (d2 = 1; d2 <= N; d2++) {
                    if (x + d1 + d2 <= N && y - d1 >= 1 && y + d2 > y && y + d2 <= N) {
                        groupMarking();
                        ans = min(ans, getMinDifference());
                    }
                }
            }
        }
    }
}

//인구 차이 최소 구함
int getMinDifference() {
    int groupPopulation[6] = {0};

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            groupPopulation[group[i][j]] += population[i][j];
        }
    }

    int populMax = 0, populMin = INT_MAX;


    for (int i = 1; i <= 5; i++) {
        if (groupPopulation[i] == 0) return INT_MAX;
        populMax = max(populMax, groupPopulation[i]);
        populMin = min(populMin, groupPopulation[i]);
    }

    return populMax - populMin;
};


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    Input();
    divideGroup();

    if (ans == INT_MAX) cout << -1 << '\n';
    else cout << ans << '\n';


    return 0;
}


void Input() {
    cin >> N;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> population[i][j];
}