[백준 17779] 게리맨더링 2

문제 바로가기

17779번: 게리맨더링 2

 

문제 미쳤냐..

x y 반대로 돼있다 ㅜㅜㅜ 하..

너무 헷갈려 !!!!

 

심지어 첫 예시가 d1 = 1, d2 = 1이여서 그냥 해보면 x, y가 바껴있다는 걸 모른다..

분명 다 맞게 했는데 왜 안되는지 엄청 헤맸는데 ㅠㅅㅠ

풀기전에 예시로 나와있는 거 다 보고 해야겠다..

어렵지는 않은데 느므 더럽다 이런문제 싫다 진짜...

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;

int N;
int people[21][21];
int map[21][21];
int population[6];
int min_diff = 100*20;
vector<pair<int, int>> base;


void find_area(int y, int x, int d1, int d2)
{
    for (int i = 0; i<= d1; i++)
    {
        map[x+i][y - i] = 5;
        map[x + d2 + i][y + d2 - i] = 5;
    }

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


    for (int i = 1; i <= N; i++)
    {
        int flag = 0;
        int start = 0, end = 0;
        for (int j = 1; j <= N; j++)
        {
            if (map[i][j] == 5 && !flag)
            {
                start = j;
                flag = 1;
            }
            else if (map[i][j] == 5 && flag)
            {
                end = j;
                flag = 0;
            }

        }

        for (int j = start + 1; j < end; j++)
            map[i][j] = 5;
    }

    //1번 구역
    for (int i = 1; i < x + d1; i++)
    {
        for (int j = 1; j <= y; j++)
        {
            if (!map[i][j])
                map[i][j] = 1;
        }
    }

    //2번 구역
    for (int i = 1; i <= x + d2; i++)
    {
        for (int j = y + 1; j <= N; j++)
        {
            if (!map[i][j])
                map[i][j] = 2;
        }
    }

    //3번 구역
    for (int i = x + d1; i <= N; i++)
    {
        for (int j = 1; j < y - d1 + d2; j++)
        {
            if (!map[i][j])
                map[i][j] = 3;
        }
    }

    //4번 구역
    for (int i = x + d2 + 1; i <= N; i++)
    {
        for (int j = y- d1 + d2; j <= N; j++)
        {
            if (!map[i][j])
                map[i][j] = 4;
        }
    }
}

int find_diff()
{
    for (int k = 1; k <= 5; k++)
    {
        int pop = 0;
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (map[i][j] == k)
                {
                    pop += people[i][j];
                }
            }
        }
        population[k] = pop;
    }

    sort(population + 1, population + 6);
    int res = population[5] - population[1];

    return res;
}
int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> people[i][j];
            base.push_back({i, j});
        }
    }

    for (pair<int,int> b: base) //기준점 x,y 정하기
    {
        for (int d1 = 1; d1 <= N; d1++)
        {
            for (int d2 = 1; d2 <= N; d2++)
            {
                memset(map, 0, sizeof(map));
                memset(population, 0, sizeof(population));

                if (d1 + d2 <= N - b.second && d2 <= N- b.first && d1 <= b.first -1)
                {
                    find_area(b.first, b.second, d1, d2);
                    min_diff = min(min_diff, find_diff());
                }
            }
        }

    }

    cout << min_diff << endl;
    return 0;
}