[백준/Python] 1184 귀농

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

1184번: 귀농

 

난이도

골드 1

 

풀이

임의의 한 점을 기준으로 분할 해준 뒤 점을 기준으로 대각선에 있는 부분의 합이 같으면 된다.

일단 한 좌표를 기준으로 분할을 한다. 가장자리를 기준으로 분할하면 크기가 0인 부분이 생기기 때문에 가장자리를 제외한다면 (N-2)^2가지 경우의 수가 있다.

그럼 다시 그 좌표를 기준으로 대각선에 있는 두 부분에서 좌표 하나를 선정해준다. 위 사진 기준으로 파란 점 4와 빨간 점 1이 같다면 가능한 경우일 것이다. 점 3개를 모두 for문을 통해 반복한다면 O(N^6)이라 시간 초과가 발생하지만 우리는 이것을 O(N^4)까지 줄일 수 있다. MITM 알고리즘과 살짝 비슷한데, 두 점에 대해 모두 반복을 돌리는 것이 아닌, 한 점에 대해 모든 결과를 구해놓고 O(N^2), 다른 한 점에 대해 구한 결과에 매칭시켜본다 O(N^2) N^2+N^2므로 O(N^2)이다. 2,3 번 면에도 동일하게 수행해준다.

2,3번 면에도 똑같이 수행해주면 된다. 한 점을 정하는 경우 O(N^2) * 그 점에 대해 가능한 경우의 수를 구함 O(N^2) 총 O(N^4)에 정답을 구할 수 있다.

 

코드

from sys import stdin
from collections import defaultdict
input=stdin.readline

def getval(sx,sy,ex,ey):
    return presum[ey][ex]-presum[sy-1][ex]-presum[ey][sx-1]+presum[sy-1][sx-1]

n=int(input())
arr=[list(map(int,input().split())) for i in range(n)]
presum=[[0]*(n+1) for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        presum[i][j]=presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+arr[i-1][j-1]

ans=0
for divy in range(1,n):
    for divx in range(1,n):
        dd=defaultdict(int)
        for i in range(1,divy+1):
            for j in range(1,divx+1):
                dd[getval(j,i,divx,divy)]+=1
        for i in range(divy+1,n+1):
            for j in range(divx+1,n+1):
                ans+=dd[getval(divx+1,divy+1,j,i)]
        dd=defaultdict(int)
        for i in range(1,divy+1):
            for j in range(divx+1,n+1):
                dd[getval(divx+1,i,j,divy)]+=1
        for i in range(divy+1,n+1):
            for j in range(1,divx+1):
                ans+=dd[getval(j,divy+1,divx,i)]
        
print(ans)