[백준/Python] 1184 귀농

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

문제 분석

난이도

플래티넘5

분류

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

문제

문제 풀이

풀이

단순히 좌표 8개를 구해주는 경우 O(N^8) (50^8)으로 시간초과가 발생한다. 임의의 한 점을 잡고 그 점에 대해서 (좌상단,우하단), (우상단, 좌하단) 이렇게 탐색을 진행해주면 O(N^4)까지 줄일 수 있다.

임의의 기준점에 맞게 누적합을 잘 이용해 풀어주면 된다. 

소스코드

from sys import stdin
from collections import defaultdict
from math import comb
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)

후기

난이도에 비해 아이디어는 어렵지 않은 문제였던 것 같다.