문제

https://www.acmicpc.net/problem/17779

나의 코드

"""

"""

from sys import stdin
input = stdin.readline

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

def d(x, y, d1, d2):
    cal = [0 for i in range(6)]
    temp = [ [0] * (n+1) for i in range(n+1) ]

    for i in range(d1+1): # 1, 3번 선거구 경계
        temp[x+i][y-i] = 5
        temp[x+d2+i][y+d2-i] = 5
    for i in range(d2+1): # 2, 4번 선거구 경계
        temp[x+i][y+i] = 5
        temp[x+d1+i][y-d1+i] = 5

    for i in range(x+1, x+d1+d2): # 5번의 선거구에 5를 넣어 구역 만들기
        isTrue = False
        for j in range(1, n+1):
            if temp[i][j] == 5:
                isTrue = not isTrue
            if isTrue:
                temp[i][j] = 5

    for r in range(1, n+1):
        for c in range(1, n+1):
            if r < x + d1 and c <= y and temp[r][c] == 0:
                cal[1] += pan[r][c]
            elif r <= x + d2 and y < c and temp[r][c] == 0:
                cal[2] += pan[r][c]
            elif x + d1 <= r and c < y - d1 + d2 and temp[r][c] == 0:
                cal[3] += pan[r][c]
            elif x + d2 < r and y - d1 + d2 <= c and temp[r][c] == 0:
                cal[4] += pan[r][c]
            elif temp[r][c] == 5:
                cal[5] += pan[r][c]

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

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):
                if 1 <= x < x + d1 + d2 <= n and 1 <= y - d1 < y < y + d2 <= n:
                    result = min(result, d(x, y, d1, d2))

print(result)

    

설명

참고 자료