파이썬으로 풀어보는 백준 17779번: 게리맨더링 2 (삼성 A형 기출 문제)

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

17779번: 게리맨더링 2

 

내 풀이:

N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
 
result = []
for i in range(N):
    for j in range(N):
        for d1 in range(1, min(j, N-i-1)+1):
            for d2 in range(1, min(N-j-1, N-i-1)+1):
                if i + d1 + d2 <= N-1:
                    value1 = 0
                    value2 = 0
                    value3 = 0
                    value4 = 0
                    value5 = 0
                    for a in range(N):
                        for b in range(N):
                            if i+j <= a+b <= i+j+2*d2 and i-j <= a-b <= i-j+2*d1:
                                value5 += arr[a][b]
                            elif 0 <= a < i+d1 and 0 <= b <= j and a+b < i+j:
                                value1 += arr[a][b]
                            elif 0 <= a <= i+d2 and j < b <= N-1 and a-b < i-j:
                                value2 += arr[a][b]
                            elif i+d1 <= a <= N-1 and 0 <= b < j - d1 + d2 and a-b > i-j+2*d1:
                                value3 += arr[a][b]
                            elif i+d2 < a <= N-1 and j-d1+d2 <= b <= N-1 and a+b > i+j+2*d2:
                                value4 += arr[a][b]
                    result.append(max(value1, value2, value3, value4, value5) - min(value1, value2, value3, value4, value5))
 
print(min(result))

Python3, 3840ms

문제의 조건을 그대로 구현하면 풀 수 있는데 문제에서 주는 x, y 좌표가 반대로 돼있고 문제에서 준 기준 역시 반대로 돼있어서 문제를 잘못 이해해서 호되게 혼난 문제이다. 평행사변형 가운데인 5번 구역을 처리해주는 게 까다로운 문제였는데 수학에서 좌표계를 이용하여 문제를 풀 듯이 조건문을 짜서 구현하였다.

 

 

blpoms님 풀이:

n = int(input())
arr = [[*map(int, input().split())] for _ in range(n)]
ans = 987654321
for d1 in range(1, n - 1):
    for d2 in range(1, n - 1):
        if d1 + d2 >= n: break
        for x in range(n - d1 - d2):
            for y in range(d1, n - d2):
                l = [0] * 5
                l[4] += arr[x][y]
                l[0] += sum([sum(arr[i][:y + 1]) for i in range(x)])
                l[1] += sum([sum(arr[i][y + 1:]) for i in range(x)])
                l[0] += sum(arr[x][:y])
                l[1] += sum(arr[x][y + 1:])
                _x_, _y, y_ = x, y, y
                if d1 == d2:
                    for _ in range(d1-1):
                        _x_, _y, y_ = _x_+1, _y - 1, y_ + 1
                        l[0] += sum(arr[_x_][:_y])
                        l[4] += sum(arr[_x_][_y:y_+1])
                        l[1] += sum(arr[_x_][y_+1:])
                    _x_, _y, y_ = _x_ + 1, _y - 1, y_ + 1
                    l[2] += sum(arr[_x_][:_y])
                    l[4] += sum(arr[_x_][_y:y_+1])
                    l[1] += sum(arr[_x_][y_+1:])
                    for _ in range(d1):
                        _x_, _y, y_ = _x_ + 1, _y + 1, y_ - 1
                        l[2] += sum(arr[_x_][:_y])
                        l[4] += sum(arr[_x_][_y:y_ + 1])
                        l[3] += sum(arr[_x_][y_+1:])
                elif d1 < d2:
                    for _ in range(d1-1):
                        _x_, _y, y_ = _x_ + 1, _y - 1, y_ + 1
                        l[0] += sum(arr[_x_][:_y])
                        l[4] += sum(arr[_x_][_y:y_ + 1])
                        l[1] += sum(arr[_x_][y_ + 1:])
                    _x_, _y, y_ = _x_ + 1, _y - 1, y_ + 1
                    l[2] += sum(arr[_x_][:_y])
                    l[4] += sum(arr[_x_][_y:y_ + 1])
                    l[1] += sum(arr[_x_][y_ + 1:])
                    for _ in range(d2-d1-1):
                        _x_, _y, y_ = _x_ + 1, _y + 1, y_ + 1
                        l[2] += sum(arr[_x_][:_y])
                        l[4] += sum(arr[_x_][_y:y_ + 1])
                        l[1] += sum(arr[_x_][y_ + 1:])
                    for _ in range(d1):
                        _x_, _y, y_ = _x_ + 1, _y + 1, y_ - 1
                        l[2] += sum(arr[_x_][:_y])
                        l[4] += sum(arr[_x_][_y:y_ + 1])
                        l[3] += sum(arr[_x_][y_ + 1:])
                else:
                    for _ in range(d2):
                        _x_, _y, y_ = _x_ + 1, _y - 1, y_ + 1
                        l[0] += sum(arr[_x_][:_y])
                        l[4] += sum(arr[_x_][_y:y_ + 1])
                        l[1] += sum(arr[_x_][y_ + 1:])
                    for _ in range(d1-d2-1):
                        _x_, _y, y_ = _x_ + 1, _y - 1, y_ - 1
                        l[0] += sum(arr[_x_][:_y])
                        l[4] += sum(arr[_x_][_y:y_ + 1])
                        l[3] += sum(arr[_x_][y_ + 1:])
                    _x_, _y, y_ = _x_ + 1, _y - 1, y_ - 1
                    l[2] += sum(arr[_x_][:_y])
                    l[4] += sum(arr[_x_][_y:y_ + 1])
                    l[3] += sum(arr[_x_][y_ + 1:])
                    for _ in range(d2):
                        _x_, _y, y_ = _x_ + 1, _y + 1, y_ - 1
                        l[2] += sum(arr[_x_][:_y])
                        l[4] += sum(arr[_x_][_y:y_ + 1])
                        l[3] += sum(arr[_x_][y_ + 1:])
                l[2] += sum([sum(arr[i][:_y]) for i in range(_x_ + 1, n)])
                l[3] += sum([sum(arr[i][y_:]) for i in range(_x_ + 1, n)])
                ans = min(ans, max(l) - min(l))
print(ans)

Python3, 352ms

d1과 d2의 관계에 따라서 어느 구역에 더해야하는 값인지를 판단하여 arr를 한 바퀴만 돌아도 문제를 풀 수 있도록 구현한 것 같다. 다만 이와 같은 풀이는 문제를 해석하는 데 시간이 오래 소요될 것으로 예상되며 코딩 길이도 내 코드의 3배가량이다.