[백준] 17779 게리맨더링 2, python

 

 

주어진 조건에 맞게 구역을 5개로 나누고, 각 구역의 인구수 총합을 구한 다음, 인구수가 가장 많은 구역과 가장 적은 구역의 인구 차이의 최솟값을 구하는 문제이다.

 

범위를 만족하는 모든 x, y, d1, d2의 경우에 대해, 각 케이스마다 구역을 나눈 뒤 인구수 차이를 구하고, 최종적으로 그 값의 최솟값을 구하면 된다.

 

처음에 격자를 생성하면서 각 row마다 누적합을 계산해 놓는다.

이후 각 구역마다 row에 해당하는 column값을 구하고 누적합을 계산한다.

 

1번 구역의 경우 1 <= r <x 범위에서 c는 y로 고정된다.

그리고 x <= r < x+d1 범위에서는 r이 1씩 커질 때마다가 c는 1씩 줄어든다.

1번 구역의 인구수의 총합은 각 row마다 1~c까지의 합을 미리 계산해 둔 누적합을 더해주면된다.

 

2번 구역의 경우는 1 <= r <= x 구간에서는 c는 y + 1로 고정된다.

x < r <= x+d2 범위까지는 r이 1씩 커질 때마다 c도 1씩 커진다.

2번 구역의 인구수 총합은 row 총합에서 1~c까지의 누적합을 빼주면 c~n까지의 합을 구할 수 있다.

 

3번 구역은 x+d1 <= r < x+d1+d2 구간까지는 r이 1씩 커질 때마다 c도 1씩 커진다.

x+d1+d2 <= r <= n 구간에서는 c는 y -d1 + d2 - 1로 고정된다.

3번도 1번과 마찬가지로 1~c까지의 누적합을 더해준다.

 

4번 구역은 x+d2 < r <= x+d1+d2 구간까지는 r이 1씩 커질 때마다 c가 1씩 감소하고,

x+d1+d2 < r <= n구간에서는 c는 y -d1 + d2로 고정된다.

4번도 2번과 마찬가지로 row의 총합에서 1~c까지의 값을 빼주면 된다.

 

5번 구역도 마찬가지로 각 r에 대해 c의 오른쪽값, 왼쪽값을 구한다.

1~오른쪽까지의 누적합에서 1~왼쪽-1까지의 누적합을 빼주면 왼쪽~오른쪽의 누적합이 나온다.

 

계산한 구역의 합에서 최댓값과 최솟값의 차이를 구하고, 전체 범위를 탐색하며 차이의 최솟값을 구한다.

 

 

import sys
input = sys.stdin.readline

n = int(input())
board = [[0]*(n+1) for _ in range(n+1)]
row_sum = [[0]*(n+1) for _ in range(n+1)]
# 격자를 생성하면서 row마다 누적합을 계산해둠
for i in range(1,n+1):
    row = list(map(int, input().split())) 
    for j in range(1,n+1):
        board[i][j] = row[j-1]
        row_sum[i][j] = row_sum[i][j-1] + row[j-1]


def diff(x,y,d1,d2):
    area_sum = [0]*6

    # 1번 구역
    for r in range(1,x+d1):
        c = y if r<x else y + (x - 1) - r
        area_sum[1] += row_sum[r][c]

    # 2번 구역
    for r in range(1,x+d2+1):
        c = y + 1 if r<=x else y + r - (x - 1)
        area_sum[2] += row_sum[r][-1] - row_sum[r][c-1]

     # 3번 구역
    for r in range(x+d1,n+1):
        c = y - d1 + d2 - 1 if r>=x+d1+d2 else (y - d1) + r - (x + d1 + 1)
        area_sum[3] += row_sum[r][c]

     # 4번 구역
    for r in range(x+d2+1,n+1):
        c = y - d1 + d2 if r>x+d1+d2 else (y + d2) - r + (x + d2 + 1)
        area_sum[4] += row_sum[r][-1] - row_sum[r][c-1]

     # 5번 구역
    for r in range(x, x+d1+d2+1):
        left = y + (x - 1) - r if r<x+d1 else (y - d1) + r - (x + d1 + 1)
        right = y + r - (x - 1) if r<x+d2 else (y + d2) - r + (x + d2 + 1)
        area_sum[5] += row_sum[r][right-1] - row_sum[r][left]

    return max(area_sum[1:]) - min(area_sum[1:])

answer = 10**16

# 모든 x,y,d1,d2에 대해 조건을 만족하는 경우 계산한 값의 최소값을 구함
for d1 in range(1,n+1):
    for d2 in range(1,n+1):
        for x in range(1,n+1):
            for y in range(1,n+1):
                if 1<= x < x+d1+d2 <= n and 1 <= y-d1 < y < y+d2 <=n:
                    answer = min(answer, diff(x,y,d1,d2))

print(answer)