게리멘더링2

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0123 ~ 03:13
// 1) 중심 x,y를 고르는 경우 = 20*20 = 400
// 2) d1,d2를 고르는 경우 < 20*20 = 400
// 3) 각 구역의 인구를 구하는 수 -> 5*(10*10)
// 총 400 * 400 * (최대 500) < 8천만 --> 완전탐색 가능!
int N,ans=1e9;
int board[25][25];
int sector[25][25];
int tot=0;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    for(int y=1;y<=N;y++)
    {
        for(int x=1;x<=N;x++)
        {
            for(int d1=1;d1<=N;d1++)
            {
                for(int d2=1;d2<=N;d2++)
                {
                    if((d1>=1 and d2>=1 and x>=1 and x<x+d1+d2 and x+d1+d2 <= N) and (y-d1>=1 and y-d1<y and y<y+d2 and y+d2<=N))
                    {
                        /* sector준비 */
                        for(int a=0;a<=22;a++)
                            fill(sector[a], sector[a]+22, 0);
                        /* 5 sector 왼쪽 위 */
                        for(int cal=0;cal<=d1;cal++)
                        {
                            int nx = x + cal;
                            int ny = y - cal;
                            sector[nx][ny] = 5;
                        }
                        /* 5 sector 왼쪽 아래 */
                        for(int cal=0;cal<=d2;cal++)
                        {
                            int nx = x + cal;
                            int ny = y + cal;
                            sector[nx][ny] = 5;
                        }
                        /* 5 sector 오른쪽 위 */
                        for(int cal=0;cal<=d2;cal++)
                        {
                            int nx = (x + d1) + cal;
                            int ny = (y - d1) + cal;
                            sector[nx][ny] = 5;
                        }
                        /* 5 sector 오른쪽 아래 */
                        for(int cal=0;cal<=d1;cal++)
                        {
                            int nx = (x + d2) + cal;
                            int ny = (y + d2) - cal;
                            sector[nx][ny] = 5;
                        }
                        int sum[6]={0,0,0,0,0,0};
                        int MIN=1e9,MAX=0;
                        /* 1 sector 수 구하기 */
                        for(int r=1;r<x+d1;r++)
                        {
                            for(int c=1;c<=y;c++)
                            {
                                if(sector[r][c] == 5) break;
                                sum[1] += board[r][c];
                            }
                        }
                        /* 2 sector 수 구하기 */
                        for(int r=1;r<=x+d2;r++)
                        {
                            for(int c=N;c>=y+1;c--)
                            {
                                if(sector[r][c] == 5) break;
                                sum[2] += board[r][c];
                            }
                        }
                        /* 3 sector 수 구하기 */
                        for(int r=x+d1;r<=N;r++)
                        {
                            for(int c=1;c<y-d1+d2;c++)
                            {
                                if(sector[r][c] == 5) break;
                                sum[3] += board[r][c];
                            }
                        }
                        /* 4 sector 수 구하기 */
                        for(int r=x+d2+1;r<=N;r++)
                        {
                            for(int c=N;c>=y-d1+d2;c--)
                            {
                                if(sector[r][c] == 5) break;
                                sum[4] += board[r][c];
                            }
                        }
                        /* 5 sector 수 구하기 */
                        sum[5] = tot - (sum[1] + sum[2] + sum[3] + sum[4]);
                        for(int q=1;q<=5;q++)
                        {
                            MIN = min(MIN, sum[q]);
                            MAX = max(MAX, sum[q]);
                        }
                        int diff = MAX - MIN;
                        ans = min(ans,diff);
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

• 로직
  • x / y / d1 / d2 가능한 모든 경우의 수에 대해 주어진 조건을 만족하는 경우를 실행
  • 1) sector 5에 해당하는 경계선을 모두 그리기
  • 2) sector 1 ~ 4에 해당하는 좌표를 탐색하며 sector별 인구수 count!
    (경계선을 만나면 다음 row로 넘어가게 시작순서를 잘 조절해야 함)
  • 3) sector 5의 수는 전체 인구수에서 1~4합을 빼면 된다
  • 앞 과정을 반복하며 최소값 갱신

• 오래걸린 이유
  : 경계를 의미하는 sector를 초기화 하는 과정에서 일부분이 자꾸 남아있어서 오류가 났었음
  --> 이런 실수때문에 간단한 문제임에도 2시간이나 소요.... 조심하자