[백준][Python] 17779 게리멘더링2

단순히 영역을 나누는 문제였습니다.

대각선에 대해 4번 범위 설정이 필요한 문제였습니다.

핵심은 1개씩 늘어나거나 줄어드는 dx, dy설정을 어떻게 할 것인가?

결국 i에서 i의 초깃값을 빼주면 0부터 시작한 다는 것을 알 수 있었습니다.

 

import sys
input = sys.stdin.readline

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
answer = float('inf')
total = 0
for i in range(N):
    for j in range(N):
        total += matrix[i][j]
for x in range(N - 1):
    for y in range(1, N - 1):
        for d1 in range(1, min(y + 1, N - x - 1)):
            for d2 in range(1, min(N - y, N - x - d1)):
                area1 = 0
                for i in range(x):
                    for j in range(y + 1):
                        area1 += matrix[i][j]
                for i in range(x, x + d1):
                    for j in range(y - d1):
                        area1 += matrix[i][j]
                for i in range(x, x + d1):
                    for j in range(y - d1, y - i + x):
                        area1 += matrix[i][j]
                area2 = 0
                for i in range(x):
                    for j in range(y + 1, N):
                        area2 += matrix[i][j]
                for i in range(x, x + d2 + 1):
                    for j in range(y + d2 + 1, N):
                        area2 += matrix[i][j]
                for i in range(x, x + d2):
                    for j in range(y + i - x + 1, y + d2 + 1):
                        area2 += matrix[i][j]

                area3 = 0
                for i in range(x + d1, N):
                    for j in range(y - d1):
                        area3 += matrix[i][j]
                for i in range(x + d1 + d2 + 1, N):
                    for j in range(y - d1, y - d1 + d2):
                        area3 += matrix[i][j]
                for i in range(x + d1 + 1, x + d1 + d2 + 1):
                    for j in range(y - d1, y - 2 * d1 + i - x):
                        area3 += matrix[i][j]
                area4 = 0
                for i in range(x + d1 + d2 + 1, N):
                    for j in range(y - d1 + d2, N):
                        area4 += matrix[i][j]
                for i in range(x + d2 + 1, x + d1 +d2 + 1):
                    for j in range(y + d2 + 1, N):
                        area4 += matrix[i][j]
                for i in range(x + d2 + 1, x + d1 + d2 + 1):
                    for j in range(y - i + x + 2 * d2 + 1, y + d2 + 1):
                        area4 += matrix[i][j]

                area5 = total - (area1 + area2 + area3 + area4)
                answer = min(answer, max(area1, area2, area3, area4, area5) - min(area1, area2, area3, area4, area5))
print(answer)