[문제풀이-백준] 17779. 게리맨더링2

풀이

시간 복잡도는 20^2*(20^2) 정도이므로 시간은 여유롭다

헤맨 부분

• 각 선거구의 번호를 정하는 수식 만들기가 힘들었음
  • 경계의 시작점을 기준으로 찾아봄
    • 1,4번 구역은 행과 열을 더한 값 이용
    • 2,3번 구역은 열-행을 이용
      • 3번: 각 행의 경계 부분의 열-행 값은 동일

팁

• 문제에서 x를 행 y를 열로 주었음
  • 문제에서 범위까지 정해주었으므로 변수명도 그대로 가져다 쓰는게 편함

=> 문제에서 행,열을 어떻게 주는지 주의 깊게 살펴볼 것

코드

# dy = [-1,0,1,0]
# dx = [0,1,0,-1]
N = int(input())
matrix = [[0] * (N + 1)] + [[0] + list(map(int,input().split())) for _ in range(N)]
answer = 9876543210
# 전체 인구수 확인
total = 0
for y in range(1,N+1):
    for x in range(1,N+1):
        total += matrix[y][x]

# 범위 정하기
for y in range(2,N): # 열
    for x 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:
                    ward = [0] * 5  # 선거구
                    # 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
                    for r in range(1, x + d1):
                        for c in range(1, y + 1):
                            if r+c < x+y:
                                ward[0] += matrix[r][c]
                    # 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
                    for r in range(1, x + d2 + 1):
                        for c in range(y + 1,N + 1):
                            if c - r > y - x:
                                ward[1] += matrix[r][c]
                    # 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
                    for r in range(x + d1, N+1):
                        for c in range(1, y-d1+d2):
                            if c - r < (y-d1) - (x+d1):
                                ward[2] += matrix[r][c]
                    # # 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
                    for r in range(x + d2 + 1, N + 1):
                        for c in range(y - d1 + d2, N + 1):
                            if r + c > (x+d2) + (y+d2):
                                ward[3] += matrix[r][c]
                    ward[4] = total - sum(ward)
                    diff = max(ward) - min(ward)
                    if diff < answer:
                        answer = diff

print(answer)