[백준 1184] 귀농 (Platinum 5)

문제

[백준] 귀농 (Platinum 5)

요약

NxN 크기의 땅이 주어지고, 각 1x1 크기의 땅(i, j)의 수익은 A(i, j)이다. 두 사람에게 땅을 나누어 주려고 한다. 두 사람이 받게 될 땅은 직사각형 모양이고 변은 축에 평행하다. 두 땅은 한 꼭짓점에서만 만나며 수익의 합이 같도록 하려고 할 때, 나누어주는 방법의 수를 구하라.

분류

• 브루트포스
• 누적 합
• 해시맵

풀이

1. 내 풀이 (브루트 포스, 누적 합, 해시 맵)

정말 “브루트 포스”스럽게 풀었다.

• 먼저 한 점에 대해 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래의 땅 수익의 합을 더한 2차원 리스트를 만들었다. (누적 합)
• 그리고 한 점을 기준으로 왼쪽 위에서 존재할 수 있는 모든 면적 합을 기록하고, 오른쪽 아래에 해당 면적이 존재한다면 cnt를 갱신시킨다.
• 오른쪽 위와 왼쪽 아래에 대해서 똑같이 진행한다.

import sys
input = sys.stdin.readline

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

leftuprightdown = [[0] * (n + 1) for _ in range(n + 1)]
rightupleftdown = [[0] * (n + 1) for _ in range(n + 1)]
rightdownleftup = [[0] * (n + 1) for _ in range(n + 1)]
leftdownrightup = [[0] * (n + 1) for _ in range(n + 1)]


for r in range(1, n + 1):
    for c in range(1, n + 1):
        leftuprightdown[r][c] = arr[r - 1][c - 1] + \
            leftuprightdown[r - 1][c] + leftuprightdown[r][c -
                                                           1] - leftuprightdown[r - 1][c - 1]

for r in range(n - 1, -1, -1):
    for c in range(1, n + 1):
        leftdownrightup[r][c] = arr[r][c - 1] + \
            leftdownrightup[r + 1][c] + leftdownrightup[r][c -
                                                           1] - leftdownrightup[r + 1][c - 1]

for r in range(1, n + 1):
    for c in range(n - 1, -1, -1):
        rightupleftdown[r][c] = arr[r - 1][c] \
            + rightupleftdown[r - 1][c] + rightupleftdown[r][c +
                                                             1] - rightupleftdown[r - 1][c + 1]

for r in range(n - 1, -1, -1):
    for c in range(n - 1, -1, -1):
        rightdownleftup[r][c] = arr[r][c] \
            + rightdownleftup[r + 1][c] + rightdownleftup[r][c +
                                                             1] - rightdownleftup[r + 1][c + 1]


cnt = 0
for i in range(1, n):
    for j in range(1, n):
        d = {}
        for r in range(i):
            for c in range(j):

                t = leftuprightdown[i][j] - leftuprightdown[r][j] - \
                    leftuprightdown[i][c] + leftuprightdown[r][c]

                try:
                    d[t] += 1
                except:
                    d[t] = 1

        for r in range(i + 1, n + 1):
            for c in range(j + 1, n + 1):

                t = rightdownleftup[i][j] - rightdownleftup[r][j] - \
                    rightdownleftup[i][c] + rightdownleftup[r][c]

                try:
                    cnt += d[t]
                except:
                    pass


for i in range(1, n):
    for j in range(1, n):
        d = {}
        for r in range(i):
            for c in range(j + 1, n + 1):

                t = rightupleftdown[i][j] - rightupleftdown[r][j] - \
                    rightupleftdown[i][c] + rightupleftdown[r][c]

                try:
                    d[t] += 1
                except:
                    d[t] = 1

        for r in range(i + 1, n + 1):
            for c in range(j):

                t = leftdownrightup[i][j] - leftdownrightup[r][j] - \
                    leftdownrightup[i][c] + leftdownrightup[r][c]

                try:
                    cnt += d[t]
                except:
                    pass

print(cnt)