17779 - 게리맨더링 2

info

• 문제 보기: 17779 - 게리맨더링 2
• 소요 시간: 💥1시간 초과
• 풀이 언어: python
• 체감 난이도: 4️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

구현

풀이 코드

info

• 메모리: 34536 KB
• 시간: 848 ms

import sys
from math import inf
input = sys.stdin.readline

n = 0
data = []

def calc(x, y, d1, d2):
    dist = [[0 for _ in range(n)] for _ in range(n)]

    # draw borders
    for i in range(d1+1):
        dist[x+i][y-i] = 5
        dist[x+d2+i][y+d2-i] = 5
    for i in range(d2+1):
        dist[x+i][y+i] = 5
        dist[x+d1+i][y-d1+i] = 5

    # district 1
    for r in range(x+d1):
        for c in range(y+1):
            if dist[r][c] == 5:
                break
            dist[r][c] = 1
    
    # district 2
    for r in range(x+d2+1):
        for c in range(n-1, y, -1):
            if dist[r][c] == 5:
                break
            dist[r][c] = 2
    
    # district 3
    for r in range(x+d1, n):
        for c in range(y-d1+d2):
            if dist[r][c] == 5:
                break
            dist[r][c] = 3
    
    # district 4
    for r in range(x+d2+1, n):
        for c in range(n-1, y-d1+d2-1, -1):
            if dist[r][c] == 5:
                break
            dist[r][c] = 4
    
    # district 5
    for r in range(n):
        for c in range(n):
            if dist[r][c] == 0:
                dist[r][c] = 5

    # calculate sum
    cnt = [0] * 5
    for r in range(n):
        for c in range(n):
            cnt[dist[r][c]-1] += data[r][c]

    return max(cnt) - min(cnt)
        
def solution():
    global n, data
    
    n = int(input())
    for _ in range(n):
        data.append(list(map(int, input().split())))
    
    ans = inf
    for x in range(n):
        for y in range(n):
            for d1 in range(1, n):
                for d2 in range(1, n):
                    if x + d1 + d2 >= n:
                        continue
                    if y - d1 < 0 or y + d2 >= n:
                        continue
                    cand = calc(x, y, d1, d2)
                    ans = min(ans, cand)

    print(ans)


if __name__ == '__main__':
    solution()

info

⚠️ 이 문제 재채점돼서 24년도 11월 이전 레퍼는 대다수가 87퍼에서 WA 받음.

그리고 처음에 제출했던 로직도 87퍼에서 틀림. 공통점이 있는듯?

반례는 다음과 같음.

9
100 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 100

answer: 77

풀이 해설

5번 선거구의 경계선을 그린 후 내부에서 BFS로 채우는 방식은 WA임. Corner case가 존재함.

🤔 5번 선거구 채우는법?

5번 선거구의 경계를 먼저 나누긴 해야 한다.

좀 고의같은데.. 문제에서 주어지는 1~4번 선거구의 범위는 5번 선거구의 영역과 겹친다.

그래서 경계부터 나눈 후에 $O(N^2)$으로 각 영역을 먼저 채워주고, 경계에 맞닿을때 break 하는 방식으로 접근한다.

flag를 두고 행 방향으로 진행하면서 5번 먼저 채울 수도 있는데, 경계의 y축 양 끝 좌표는 로직에서 제외되어야 하므로 이거 계산해야돼서 더 구림.

메모

• 이 문제 풀다가 죽을뻔;