275. 게리맨더링 2

백준

1. Python

import copy

INF = 1e9


def solve(x, y, d1, d2):
    temp = [[0] * (n + 1) for _ in range(n + 1)]
    # 2번 조건
    temp[x][y] = 5
    for i in range(1, d1 + 1):
        temp[x + i][y - i] = 5
    for i in range(1, d2 + 1):
        temp[x + i][y + i] = 5
    for i in range(1, d2 + 1):
        temp[x + d1 + i][y - d1 + i] = 5
    for i in range(1, d1 + 1):
        temp[x + d2 + i][y + d2 - i] = 5

    people = [0] * 5
    # 1번 선거구
    for r in range(1, x + d1):
        for c in range(1, y + 1):
            if temp[r][c] == 5:
                break
            else:
                people[0] += maps[r][c]

    # 2번 선거구
    for r in range(1, x + d2 + 1):
        for c in range(n, y, -1):
            if temp[r][c] == 5:
                break
            else:
                people[1] += maps[r][c]

    # 3번 선거구
    for r in range(x + d1, n + 1):
        for c in range(1, y - d1 + d2):
            if temp[r][c] == 5:
                break
            else:
                people[2] += maps[r][c]

    # 4번 선거구
    for r in range(x + d2 + 1, n + 1):
        for c in range(n, y - d1 + d2 - 1, -1):
            if temp[r][c] == 5:
                break
            else:
                people[3] += maps[r][c]

    # 5번 선거구
    people[4] = total - sum(people)
    return max(people) - min(people)


if __name__ == "__main__":
    n = int(input())
    maps = [[0] * (n + 1)] + [[0] + list(map(int, input().split())) for _ in range(n)]

    total = 0
    for i in range(1, n + 1):
        total += sum(maps[i])

    answer = INF
    for x in range(1, n + 1):
        for y in range(1, n + 1):
            for d1 in range(1, n + 1):
                for d2 in range(1, n + 1):
                    # 1번 조건
                    if x + d1 + d2 > n:
                        continue
                    if y - d1 < 1:
                        continue
                    if y + d2 > n:
                        continue

                    answer = min(answer, solve(x, y, d1, d2))

    print(answer)

메모리 사용 감소

import sys
input = sys.stdin.readline

n = int(input())
data =  [[0] * (n + 1)] + [[0] + list(map(int, input().split())) for _ in range(n)]


cnt = 0
minval = sys.maxsize

def make_boundary(x,y,d1,d2):
    global minval
    zone = [0] * 5

    #1번구역
    val = y
    for i in range(1, x+d1):#행
        if i >= x : val -=1
        for j in range(val,0, -1):
            #print(i,j)
            zone[0] += data[i][j]
    #2번구역
    val = 0
    for i in range(1, x+d2+1):
        if i > x : val += 1
        for j in range( y+1+val, n+1, 1):
            zone[1] += data[i][j]
    #3번구역
    val = y-d1-1
    for i in range(x+d1, n+1):
        if i <= x + d1 + d2 : val += 1
        for j in range(1, val):
            zone[2] += data[i][j]

    #4번구역
    val = y+d2
    for i in range(x+d2+1, n+1):
        for j in range(val, n+1):
            zone[3] += data[i][j]
        if i <= x+d1+d2: val-=1

    #5번구역
    left, right = y,y
    for i in range(x, x+d1+d2+1):
        for j in range(left, right+1):
            zone[4] += data[i][j]
        if i < x+d1 : left -=1
        else : left += 1
        if i < x+d2 : right += 1
        else : right -= 1

    minval = min(minval, max(zone) - min(zone))

for y in range(2, n):
    for x in range(1, n-1):
        for d2 in range(1, n - y + 1):
            for d1 in range(1, min(n-(x+d2) + 1, y)):
                make_boundary(x,y,d1,d2)

print(minval)