[python] 17779 - 게리맨더링 2

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

17779번: 게리맨더링 2

 

 

정답률 56.270%

난이도 골4

왜 정답률이 높은지 모르겠음 범위 설정이나 예외처리가 까다롭..ㅠ

 

---

코드 설명

1. 입력 받기

2. 각 x, y, d1, d2마다 인구 수 계산

3. 인구 경계

4. 정답 갱신

 

 

※ 주의할 점

• 여러 조건들 이용해서 for문 반복횟수 줄이기
• 정답 초기값은 문제 조건에서 최대로 나올 수 있는 경우 간단하게 계산(N=20, 전부 100명인데 전부 1번 선거구)
• 5번 선거구의 경계 구할 때 방정식을 이용해서 구했는데 x, y축을 2차원 함수 구할때와 다르게 설정했다는 거 주의
  (우상향 직선이 기울기 -1)
• 경계의 왼쪽 꼭짓점이 y=0일때 그 행에서 3구역 인구수 구하면 인덱스가 -1로 설정됨 -> 누적합 맨 끝에 0 추가
  이렇게 구현 안했어도 꼭짓점 근처 예외처리(특히 꼭짓점이 상하좌우 끝쪽에 배치될 때)는 꼭 확인해보기
• d1 > d2, d1 < d2 둘다 잘 되는지도 확인해보기

# 3. 인구 경계
def count(d1, d2, x1, y1):
    cnt = [0] * 5
    for r in range(N):
        # 기준점 위
        if r < x1:
            cnt[0] += cboard[r][y1]
            cnt[1] += cboard[r][N - 1] - cboard[r][y1]
        # 기준점 아래
        elif r > x1 + d1 + d2:
            cnt[2] += cboard[r][y1 - d1 + d2 - 1]
            cnt[3] += cboard[r][N - 1] - cboard[r][y1 - d1 + d2 - 1]
        # 사각형 안쪽
        else:
            # 기준점 왼쪽 위
            if x1 <= r < x1 + d1:
                cnt[0] += cboard[r][-r + x1 + y1 - 1]
            # 기준점 왼쪽 아래
            else:
                cnt[2] += cboard[r][r - x1 + y1 - 2 * d1 - 1]
            # 기준점 오른쪽 위
            if x1 <= r <= x1 + d2:
                cnt[1] += cboard[r][N - 1] - cboard[r][r - x1 + y1]
            # 기준점 오른쪽 아래
            else:
                cnt[3] += cboard[r][N - 1] - cboard[r][-r + x1 + y1 + 2 * d2]
    
    # 5번 선거구는 전체에서 빼기
    cnt[4] = total - cnt[0] - cnt[1] - cnt[2] - cnt[3]
    return max(cnt) - min(cnt)



# 1. 입력 받기
N = int(input())
board = []          # 입력으로 주어지는 인구 수
cboard = []         # 행 기준 누적 합
total = 0
ans = 40000         # 최댓값 = 20 * 20 * 100

for i in range(N):
    temp1 = list(map(int, input().split()))
    temp2 = [temp1[0]]
    for j in range(N - 1):
        temp2.append(temp1[j + 1] + temp2[j])
    temp2.append(0)     # 예외처리: 인덱스에서 -1을 가리키거나 N을 가리킬 때 0으로 만들기 위해서
    total += temp2[N - 1]
    board.append(temp1)
    cboard.append(temp2)

# 2. 각 x, y, d1, d2마다 인구 수 계산
# 조건들 이용해서 for문 반복수 줄이기
for d1 in range(1, N - 1):
    for d2 in range(1, N - d1):
        for x in range(N - d1 - d2):
            for y in range(d1, N-d2):
                now = count(d1, d2, x, y)
                # 4. 정답 갱신
                if now < ans:
                    ans = now

print(ans)

 

 

---

코드 결과