17779 - 게리맨더링 2

 

---

 

문제

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

17779번: 게리맨더링 2

 

풀이

구현.. 그냥 싹 다 구현인 문제다. 

나처럼 풀이하는게 맞는 방법인지는 모르겠으나, 섬세하게 코드 짜지않으면 바로 틀려버리는 문제.. 

 

문제 같은 경우에는 d1과 d2이 가질 수 있는 모든 경우의 수와, 기준점이 될 수 있는 점의 좌표를 넣어 하나씩 모두 계산해본다음 최솟값을 찾는 방식으로 접근했다.

 

초반에 탐색 시간을 조금이라도 더 줄여볼려고, 짜잘한 테크닉을 썼다.

조건과 예시 사진의 형태를 보면 기준점을 가장 위로, 다이아몬드 형식의 경계를 지니고 있다. d1, d2가 1이더라도 왼쪽이나 오른쪽, 아래쪽으로 여유 공간이 있어야 한다. 

위에 표시한 행이나 열들은 d1, d2가 1일때에도 여유 공간이 부족하기에 애초에 배제하고 시작했다.

 

또한 d1, d2의 최대크기는 n에 의해 결정될것이다. n이 7일때는 6까지 최대 경우의 수를 만들면 된다. (6,2 까지 가능)

 

이후에 나는 5의 경계를 설정하고 1 -> 2 -> 3 -> 4 순으로 공간을 나누고, 값을 책정해줬다.

5의 경계를 설정해줄 때 인덱스가 늘어났다 줄어들었다 하는 부분을 잘 신경쓰고,

1,2,3,4 같은 경우에는 반복문의 경계를 잘 설정해 돌리되 5가 있는곳은 break 하거나 continue 하는 식으로 빠져나오게 했다.

 

코드

import itertools
from sys import stdin
import sys


def getFifth(x, y, d1, d2, area):
    fifth = 0
    start = end = y
    cnt1 = 0
    cnt2 = 0
    d1_cnt = 0
    d2_cnt = 0
    for i in range(x, x+d1+d2+1):
        for j in range(start+cnt1, end+cnt2+1):
            area[i][j] = 5
            fifth += people[i][j]

        # d1만큼 이동했다면, 앞에 좌표는 더해준다. 그전에는 빼주고
        if d1_cnt < d1:
            cnt1 -= 1
        else:
            cnt1 += 1

        if d2_cnt < d2:
            cnt2 += 1
        else:
            cnt2 -= 1

        d1_cnt +=1
        d2_cnt +=1

    return area, fifth
def getFirst(x, y, d1, d2, area):
    global people
    # x + d1번 반복하면 된다.
    # 만약 5를 만나면 break, 아니라면 y까지 해주면 된다.
    first = 0
    for i in range(x+d1):
        for j in range(y+1):
            if area[i][j] == 5 or j >= y+1:
                break
            else:
                area[i][j] = 1
                first += people[i][j]
    return area, first
def getSecond(x, y, d1, d2, area):
    global people
    second = 0
    for i in range(x+d2+1):
        for j in range(y+1, n):
            if area[i][j] == 5: continue
            else:
                area[i][j] = 2
                second += people[i][j]
    return area, second
def getThird(x, y, d1, d2, area):
    global people
    third = 0
    for i in range(x+d1, n):
        for j in range(y-d1+d2):
            if area[i][j] == 5 : break
            else:
                area[i][j] = 3
                third += people[i][j]
    return area, third
def getFourth(x, y, d1, d2, area):
    global people
    fourth = 0
    for i in range(n-1, x+d2, -1):
        for j in range(y-d1+d2, n):
            if area[i][j] == 5: continue
            else:
                area[i][j] = 4
                fourth += people[i][j]
    return area, fourth

def getPartValue(x, y, d1, d2):
    global people, n, answer
    area = [ [0] * n for _ in range(n) ]
    if 0<= x+d1 < n and 0 <= y-d1 < n and \
            0<= x+d1+d2 < n and 0 <= y-d1+d2 < n and \
            0<= x+d2 < n and 0 <= y+d2 < n:

        area, fifth = getFifth(x, y, d1, d2, area)
        area, first = getFirst(x, y, d1, d2, area)
        area, second = getSecond(x, y, d1, d2, area)
        area, third = getThird(x, y, d1, d2, area)
        area, fourth = getFourth(x, y, d1, d2, area)

        maximum = max(first, second, third, fourth, fifth)
        minimum = min(first, second, third, fourth, fifth)
        answer = min(answer, maximum - minimum)
    else:
        return

answer = sys.maxsize
n = int(input())
people = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(n) ]
boundary = []
for i in range(1, (n-1)):
    boundary.append(i)
permu = itertools.product(boundary, repeat=2)

for p in permu:
    for i in range(0, n-2):
        for j in range(1, n-1):
            getPartValue(i, j, p[0], p[1])

print(answer)

 

후기

 

오히려 너무 단순 구현이라 반례가 별로 없었다. 

처음에는 범위 한개를 잘못설정해서 틀렸었고,

두번째에는 데카르트곱(itertools.product) 을 써야하는데 조합을 쓰고 있었다. 

저번에 순열 써야할때는 조합을 쓰더니 이번에도 쇼했다.

 

오히려 이런 문제가 진짜 기빠지고 힘든 거 같다. 정형화된 패턴이 없는 문제들..