[BOJ] 17779번 - 게리맨더링2(삼성 SW 기출)

하루에 한 문제씩 계속해서 풀고있지만, 여전히 문제 하나하나가 어렵게 느껴진다. 좀 낮은 단계씩 차근차근 다시 풀어볼까.. 생각중이다.

친구들도 한 번 씩 보니 나만 그렇게 어렵다고 느낀게 아니라 다행이기도 하다. ㅋ.ㅋ

 

무엇보다 어떤 문제들을 봤을 때 어떤 알고리즘을 적용하는지, 어떻게 구현 할지 이 두가지를 동시에 길러내기 위해서 여러 문제를 풀어보고

부족한 유형을 풀어보면서 실력을 키워나가야 한다.

 

항상 얘기했지만, 문제를 잘 못 이해하는순간 1시간은 기본으로 날아간다고 보면 된다. 이 문제를 꼼꼼히 읽어보지 않고, 좌표 값 대충 잡아서 디버깅 하는 데만 진짜 1시간 넘게 걸렸던 것 같다. 아직 행렬에 관해서 편하게 자유자재로 다룰 수 있는 능력이 되지 않는 것 같아 몇 문제 더 풀어 볼 예정이다.

 

www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

문제를 다 읽고, 주어진 변수 들의 범위를 보면 대충 어떤 알고리즘을 적용 할 지 감을 잡을 수 있다.

예를 들어 이분탐색은 억 단위가 넘어 갈 수 있고, 10만~ 되면 N^2으로는 풀 수 없으니 한 번 순회하는 dp 라던지 이런 방법?들을 생각 해 볼 수 있다.

 

이번 문제는 N의 범위가 5 <= N <=20 이므로 구현위주로 잘 짜주기만 하면 될 것 같았다. 

 

d1,d2의 값들은 해당 범위 내에서 중복조합을 해주면 될것 같다!

 

1. 주어진 문제의 범위를 이용해 경계선 긋기

 

2. 경계선과 문제의 범위를 이용하여 구역 나누기

 

3. 나눠진 범위를 토대로 구역별 인구수의 최댓 값 최솟 값 차이 구하기

 

 

여기서 주목해야할 것은 2번이다. 경계선을 기준으로 구역의 번호를 매겨야하는데 어떻게 매길 것인가?

글쓴이는 이렇게 했다.

 

구역별 순회

각 구역별 순회를 행 기준으로 하되, 2, 4구역은 column(열) 을 역으로 순회 했다.

순회를 하면서 5번을 만나면 break 하면서 다음 행 순회 (각 구역별 범위는 정해져 있다!)

 

3번은 사실 구역별 순회를 하면서 번호를 매김과 동시에 그 구역 인구수를 list에 담아 저장 해놨다.

고로 5번 구역의 사람들만 따로 구해주면 구역별 인구수가 나올 것이다.

 

 

from sys import stdin

std = stdin.readline

N = int(std())

people, region = [], []

for i in range(N):
    people.append(list(map(int, std().split())))


check = [0 for i in range(N)]
xy = []
base = []
answer = 400000


def combi():
    if len(xy) == 2:
        base.append(list(xy))
        return

    for i in range(1, N):
        xy.append(i)
        combi()
        xy.pop()


combi()


def divide(r, c, D1, D2):
    for i in range(D1+1):
        region[r+i][c-i] = 5
        region[r+D2+i][c+D2-i] = 5
    for i in range(D2+1):
        region[r+i][c+i] = 5
        region[r+D1+i][c-D1+i] = 5


def re_divide(r, c, D1, D2):
    how = [0 for i in range(5)]

    for i in range(r+D1):
        for j in range(c+1):
            if region[i][j] == 5:
                break
            region[i][j] = 1
            how[0] += people[i][j]

    for i in range(r+D2+1):
        for j in range(N-1, c, -1):
            if region[i][j] == 5:
                break
            region[i][j] = 2
            how[1] += people[i][j]

    for i in range(r+D1, N):
        for j in range(c-D1+D2):
            if region[i][j] == 5:
                break
            region[i][j] = 3
            how[2] += people[i][j]

    for i in range(r+D2+1, N):
        for j in range(N-1, c-D1+D2-1, -1):
            if region[i][j] == 5:
                break
            region[i][j] = 4
            how[3] += people[i][j]

    for i in range(N):
        for j in range(N):
            if region[i][j] == 5 or region[i][j] == 0:
                how[4] += people[i][j]

    return max(how) - min(how)


for i in range(N):
    for j in range(N):
        x, y = i, j
        for d1, d2 in base:
            if x + d1+d2 < N and y + d2 < N and y-d1 >= 0:
                region = [[0 for _ in range(N)] for __ in range(N)]
                divide(x, y, d1, d2)
                ans = re_divide(x, y, d1, d2)
                if ans < answer:
                    answer = ans

print(answer)