[백준][구현] 게리멘더링 2

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

17779번: 게리맨더링 2

 

내가 작성한 코드

from collections import defaultdict, deque

def read_data():
    N = int(input().rstrip())
    board = []
    total = 0
    for r in range(N):
        board.append(list(map(int, input().rstrip().split())))
        total += sum(board[r])
    return N, board, total

def get_sector1(board, N, x, y, d1, d2):
    total = 0
    for r in range(x+d1):
        for c in range(y+1-(r - x +1if r >= x else 0)):
            # print(r, c)
            total += board[r][c]
    return total

def get_sector2(board, N, x, y, d1, d2):
    total = 0
    for r in range(x+d2+1):
        for c in range(y+1-(x-r if r>=x else 0), N):
            # print(r, c)
            total += board[r][c]
    return total

def get_sector3(board, N, x, y, d1, d2):
    total = 0
    for r in range(x+d1, N):
        for c in range(y-d1+d2 -((x+d1+d2-r) if r < x+d1+d2 else 0)):
            # print(r, c)
            total += board[r][c]
    return total

def get_sector4(board, N, x, y, d1, d2):
    total = 0
    for r in range(x+d2+1, N):
        for c in range(y-d1+d2 +((x+d1+d2)-r+1 if r <= x+d1+d2 else 0), N):
            # print(r, c)
            total += board[r][c]
    return total

def get_answer(N, board, total):
    mn = float('inf')
    for x in range(N):
        for y in range(N):
            for d1 in range(1, N):
                for d2 in range(1, N):
                    if not (x < x+d1+d2 < N):
                        continue
                    if not (0 <= y-d1 < y < y+d2 < N):
                        continue
                    one = get_sector1(board, N, x, y, d1, d2)
                    two = get_sector2(board, N, x, y, d1, d2)
                    three = get_sector3(board, N, x, y, d1, d2)
                    four = get_sector4(board, N, x, y, d1, d2)
                    five = total - sum([one, two, three, four])

                    mn = min(mn, max(one, two, three, four, five) - min(one, two, three, four, five))
    return mn

def test():
    N = 20
    board = [[0 for _ in range(N)] for _ in range(N)]
    return N, board

N, board, total = read_data()
# N, board = test()
print(get_answer(N, board, total))


# get_sector1(board, N, 1, 3, 2, 2)
# get_sector1(board, N, 1, 4, 3, 2)
# get_sector4(board, N, 3, 2, 1, 1)

• 1~4 선거구 구하는 함수 작성
  
  • 조건식을 보면서 r, c의 for문 작성
  • (r, c)를 찍어보면서, 그림과 비교
  • row 기준
    - 최상단 x 부터 변하는 c값 계산
    - 최하단 x+d1+d2부터 변하는 c값 계산
• 5 선거구
  • 인구수 : (전체 인구의 합) - (1~4선거구 인구의 합)
• x, y, d1, d2
  • x, y 범위 : 0 ~ N-1
  • d1, d2 범위 : 1 ~ N-1
  • 4중 for문으로 조건 만족하지 않을시 continue
    • x < x+d1+d2 < N
    • 0 <= y-d1 < y < y+d2 < N

 

다른 사람이 작성한 코드

None

• 강한 구현문제로 다른 코드를 참고하지 않음

 

기억해야할 것

• 까다로운 격자 범위 문제
  • 지정하는 범위를 복잡한 식으로 표현
  • 모든 식을 계산하지 않고, 범위 내의 모든 값으로 탐색
  • 조건을 비교