[BaekJoon] 백준 17779번 게리맨더링 2

[BaekJoon] 백준 17779번 게리맨더링 2

 

🎈문제

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

💬설명

• 삼성 기출이라 시간재고 풀었더니 1시간 30분정도 걸렸다. 구현문제라 어렵진 않았는데 5번 구역을 구하는 부분에서 꽤 애먹었다. 더 깔끔하게 구할 수 있을 것 같은데..
• 문제에서 주어지는 구역들의 범위 ..<= x <=..를 잘 활용하는게 중요한 것 같다.
• 풀이 과정
  1. 가능한 x, y, d1, d2 조합을 for문으로 돌린다.
  2. 조합 별로 선거구의 인원수를 계산해서 (인구 가장 많은 선거구 - 인구 가장 적은 선거구)의 값을 구한다.
  3. 최소값을 update 한다.

👩‍💻코드

# BaekJoon17779.py

answer = float('inf')
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
    A[i] = list(map(int, input().split()))


def divide(x, y, d1, d2):
    global N, A
    number = [0, 0, 0, 0, 0]
    divided = [[0 for _ in range(N)] for _ in range(N)]

    # 5번 구역 구하기
    for i in range(d1 + 1):
        if divided[x + i][y - i] == 5 or divided[x + d2 + i][y + d2 - i] == 5:
            continue
        divided[x + i][y - i] = 5
        divided[x + d2 + i][y + d2 - i] = 5
        number[4] += A[x + i][y - i]
        number[4] += A[x + d2 + i][y + d2 - i]

    for i in range(d2 + 1):
        if divided[x + i][y + i] == 5 or divided[x + d1 + i][y - d1 + i] == 5:
            continue
        divided[x + i][y + i] = 5
        divided[x + d1 + i][y - d1 + i] = 5
        number[4] += A[x + i][y + i]
        number[4] += A[x + d1 + i][y - d1 + i]

    for i in range(x + 1, x + d1 + d2):
        is_five = False
        for j in range(N):
            if divided[i][j] != 5 and is_five:
                number[4] += A[i][j]
                divided[i][j] = 5
            elif divided[i][j] == 5 and not is_five:
                is_five = True
            elif divided[i][j] == 5 and is_five:
                break

    # 나머지 구역 구하기
    for i in range(N):
        for j in range(N):
            if divided[i][j] == 5:
                continue
            if 0 <= i < x + d1 and 0 <= j <= y:
                number[0] += A[i][j]
            elif 0 <= i <= x + d2 and y < j < N:
                number[1] += A[i][j]
            elif x + d1 <= i < N and 0 <= j < y - d1 + d2:
                number[2] += A[i][j]
            elif x + d2 < i < N and y - d1 + d2 <= j < N:
                number[3] += A[i][j]

    return max(number) - min(number)


for x in range(1, N - 1):
    for y in range(1, N - 1):
        for d1 in range(1, y):
            for d2 in range(1, N - y):
                # 구역을 벗어나는 경우
                if d1 + d2 > N - 1 - x:
                    continue

                # 최소값 구하기
                answer = min(answer, divide(x, y, d1, d2))

print(answer)

# 좀더 깔끔하게 정리한 코드
# BaekJoon17779.py

answer = float('inf')
N = int(input())
A = [[] for _ in range(N)]
total = 0
for i in range(N):
    A[i] = list(map(int, input().split()))
    total += sum(A[i])


def divide(x, y, d1, d2):
    global N, A, total
    number = [0, 0, 0, 0, 0]
    divided = [[0 for _ in range(N)] for _ in range(N)]

    # 5번 구역 구하기

    # 5번 구역 경계선 표시
    for i in range(d1 + 1):
        divided[x + i][y - i] = 5
        divided[x + d2 + i][y + d2 - i] = 5
    for i in range(d2 + 1):
        divided[x + i][y + i] = 5
        divided[x + d1 + i][y - d1 + i] = 5

    # 5번 구역 내부 표시하기
    for i in range(x + 1, x + d1 + d2):
        first_five = divided[i].index(5)
        second_five = first_five + divided[i][first_five + 1:].index(5) + 1

        for j in range(first_five, second_five + 1):
            divided[i][j] = 5

    # 나머지 구역 구하기
    for i in range(N):
        for j in range(N):
            if divided[i][j] == 5:
                continue
            if 0 <= i < x + d1 and 0 <= j <= y:
                number[0] += A[i][j]
            elif 0 <= i <= x + d2 and y < j < N:
                number[1] += A[i][j]
            elif x + d1 <= i < N and 0 <= j < y - d1 + d2:
                number[2] += A[i][j]
            elif x + d2 < i < N and y - d1 + d2 <= j < N:
                number[3] += A[i][j]

    number[4] = total - sum(number)
    return max(number) - min(number)


for x in range(1, N - 1):
    for y in range(1, N - 1):
        for d1 in range(1, y):
            for d2 in range(1, N - y):
                # 구역을 벗어나는 경우
                if d1 + d2 > N - 1 - x:
                    continue

                # 최소값 구하기
                answer = min(answer, divide(x, y, d1, d2))

print(answer)