[코테준비] 10. 백준- 게리맨더링 2 (17779) python "삼성 SW 역량 테스트 기출 문제"

게리맨더링 2

• 링크:https://www.acmicpc.net/problem/17779
• 난이도:골드 3
• 분류: 구현, 시뮬레이션, 브루트포스 알고리즘
• 직접 푼 여부: X - 블로그를 보고 풀다가 이해가 안되는 것들은 다 내가 이해한대로 수정해서 풀었다.

풀이 노트

• 제약조건들은 문제에 나온대로 해주면 된다. 처음에 문제를 이해하는데 시간이 오래 걸렸다.
• 예시 그림에서 3,4 구역이 어디부터 시작하는지 주의해서 보자! ( 1,2 구역이 어디까지인지) 딱 중앙을 못 나누니까 하나가 더 넓게 사용하고 있으니 가로 세로 각각 어디서 누가 더 많은 영역을 차지하는지 주의해서 볼 것 !

문제 풀이의 흐름

1. input 받기

2. 가능한 r,c,d1,d2 고르기 (def check)

3. 가능한 곳들 인구수 계산해서 비교하기 (def calculate)

 

풀면서 작성한 생각노트

문제이해를 위해서 그림을 그려보았다.

각 구역마다 구간을 생각해보았다. 그런데 오류가 좀 있다. ex) c: "작을 때 만"은 3일때 맞고, 4일때는 "같거나 작을 때"이다.

• 참고한 곳: https://velog.io/@djagmlrhks3/Algorithm-BaekJoon-17779.-%EA%B2%8C%EB%A6%AC%EB%A7%A8%EB%8D%94%EB%A7%81-2-by-Python
• 그런데, 해당 코드에서 이해 안되는 것들이 있어서, 그것은 문제에 나온대로 내가 직관적으로 이해한대로 수정하였다. 

 

정답코드 💻

# 게리맨더링
# 참고: https://velog.io/@djagmlrhks3/Algorithm-BaekJoon-17779.-%EA%B2%8C%EB%A6%AC%EB%A7%A8%EB%8D%94%EB%A7%81-2-by-Python

import sys
input = sys.stdin.readline

n = int(input())
mapp = [list(map(int, input().split())) for _ in range(n)]
total =0
for row in mapp:
    total += sum(row)
    
answer = int(1e9)

def population(row, col, d1, d2):
    global total, answer
    one , two, three, four =0,0,0,0
    
    #각각 구역 인구수 구하기
    #1
    col1 = col +1
    for r in range(row+d1):
        if r>=row:
            col1 -=1
        one +=sum(mapp[r][:col1])
    #2
    col2= col+1
    for r in range(row+d2+1):
        if r> row:
            col2+=1
        two+= sum(mapp[r][col2:])
    # 3
    col3 = col-d1
    for r in range(row+d1, n):
        three+= sum(mapp[r][:col3])
        if r < row+d1+d2:
            col3 +=1
    #4
    col4 = (col+d2)
    for r in range(row+d2+1, n):
        four+=sum(mapp[r][col4:])
        if r<=row+d1+d2:
            col4-=1
    # 5
    five = total -one-two-three-four
    answer = min(answer, (max(one,two,three,four,five) - min(one,two,three,four,five)))

def check(r,c, d1, d2):
    #가능한 d1, d2 찾기 -> 문제에 주어진 조건 중 당연한 것 빼고
    if 1<=r+d1+d2<=n and 1<=c-d1<c<c+d2 and c+d2<=n:
        population(r,c,d1,d2)
        
# main 문 -> check -> population   
# 사실 다 0~n-1까지하고, check에서 조건으로 검사해도 되지만, 그럼 시간효율이 떨어지니까 확실히 안되는 경우의 수는 미리 제거!
for r in range(n-2): # d1+d2가 뒤에 들어가야하니까 2자리 남기기
    for c in range(1, n-1): # 앞에 d1, 뒤에 d2가 들어가야하니까 각각 1씩 빼줌
        for d1 in range(1,n-1): # 적어도 1이고, d2도 들어가야하니까 -1
            for d2 in range(1, n-1): # d1과 동일한 조건
                check(r,c,d1,d2)

print(answer)