2019_하_A_1_L13

종전

Simulation

평균 : 180'

---

sol : 190' 08''

• 수행 시간 : 295ms
• 메모리 : 23MB

• New skills
  Backtracking은 진짜 죄악일 수도 있구나.
  오히려 4중 for문을 돌리는 게 시간을 훨씬 더 절약했다.
  왜냐, 백트래킹은 재귀 호출 / 리턴 스택 오버헤드 제거를 하는 데 필요한 상수 시간복잡도가 꽤 많이 잡아먹었다. 따라서 단순히 4중 for문을 돌리는 게 상수항이 사라짐으로써 훨씬 빨라진 것이다.

• 이론상 Backtracking이나 4중 for문이나 시간복잡도는 O(N^4)이었다.
  왜냐, 어쨌든 점 4개에 대해 backtracking을 한다 해도 결국 n^4이니까.
  따라서 시간 초과가 난 상황에 대해서 시간복잡도를 생각해보고, 만약 동일하다면 BT보단 4중 for문이 더 나을 수도 있다는 걸 생각해야 한다.

• Tips)
  너무 수학적으로 해결할 생각하지 말자. 네 개 꼭짓점 좌표에 대해 수식으로 정리하고 들어가려고 하니까 여기에만 1시간을 쏟게 되었다. 실제 로직은 그렇게 수학적 이론이 필요하진 않은 것 같으니, 마음 편하게 먹고 풀자.

import sys

n = int(input())
world = [list(map(int, input().split())) for _ in range(n)]

answer = sys.maxsize
def d_pos():
    global answer
    for di in range(2, n):
        for dj in range(1, n - 1):
            for a in range(1, n):
                for b in range(1, n):
                    ri, rj = di - a, dj + a
                    ui, uj = di - a - b, dj + a - b
                    li, lj = di - b, dj - b
                    if is_inbound(ri, rj) and is_inbound(ui, uj) and is_inbound(li, lj):
                        answer = min(answer, get_tribes([[di, dj], [ri, rj], [ui, uj], [li, lj]]))


def is_inbound(r, c):
    if 0 <= r < n and 0 <= c < n:
        return True
    return False


def get_tribes(points):
    d, r, u, l = points[0], points[1], points[2], points[3]
    t1, t2, t3, t4, t5 = 0, 0, 0, 0, 0

    # tribe 2 - fin
    i_depth_t2 = u[0] - 1
    for col in range(u[1], -1, -1):
        if col >= l[1]:
            i_depth_t2 += 1
        for row in range(0, i_depth_t2):
            t2 += world[row][col]

    # tribe 3 - fin
    i_depth_t3 = u[0]
    for col in range(u[1] + 1, n):
        if col <= r[1] + 1:
            i_depth_t3 += 1
        for row in range(0, i_depth_t3):
            t3 += world[row][col]

    # tribe 4 - fin
    i_height_t4 = d[0] + 1
    for col in range(d[1] - 1, -1, -1):
        if col >= l[1] - 1:
            i_height_t4 -= 1
        for row in range(i_height_t4, n):
            t4 += world[row][col]

    #tribe 5
    i_height_t5 = d[0] + 2
    for col in range(d[1], n):
        if col <= r[1]:
            i_height_t5 -= 1
        for row in range(i_height_t5, n):
            t5 += world[row][col]

    # tribe 1
    total = 0
    for i in range(n):
        for j in range(n):
            total += world[i][j]
    t1 = total - (t2 + t3 + t4 + t5)

    return max(t1, t2, t3, t4, t5) - min(t1, t2, t3, t4, t5)

d_pos()
print(answer)