[BOJ] 17779 - 게리맨더링 2 (Python)

 

 

아이디어

 

완전 탐색으로 접근하되, 누적합을 이용하여 각 선거구의 인구 합을 빠르게 계산한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    total = 0
    for i in range(N):
        for j in range(1, N):
            A[i][j] += A[i][j-1]
        A[i] = [0]+A[i]
        total += A[i][-1]
    res = total
    for r in range(N-2):
        for c in range(1, N-1):
            for d1 in range(1, min(N-r-1, c+1)):
                for d2 in range(1, min(N-(r+d1), N-c)):
                    P = [0]*5
                    for i in range(r):
                        P[0] += A[i][c+1]
                    for i in range(d1):
                        P[0] += A[r+i][c-i]
                    for i in range(r+1):
                        P[1] += A[i][N]-A[i][c+1]
                    for i in range(d2):
                        P[1] += A[r+i+1][N]-A[r+i+1][c+2+i]
                    for i in range(d2):
                        P[2] += A[r+d1+i][c-d1+i]
                    for i in range(r+d1+d2, N):
                        P[2] += A[i][c-d1+d2]
                    for i in range(d1):
                        P[3] += A[r+d2+i+1][N]-A[r+d2+i+1][c+d2-i]
                    for i in range(r+d1+d2+1, N):
                        P[3] += A[i][N]-A[i][c-d1+d2]
                    P[4] = total-sum(P)
                    temp = max(P)-min(P)
                    if temp < res:
                        res = temp
    print(res)

solution()