BOJ 20002번: 사과나무

www.acmicpc.net/problem/20002

20002번: 사과나무

아이디어: 

2차원 배열의 누적합을 구했던 문제를 참고하여 풀었다.

1X1 크기의 정사각형 밭의 합은 입력 때 받은 배열과 일치하므로 입력을 받으면서 최댓값을 갱신했고,

K=2~N까지로 잡고 for 문을 돌려서 (i,j)를 왼쪽 위 꼭짓점으로 하는 KXK크기의 정사각형의 부분합을 구하며 최댓값을 갱신했다.

 

파이썬은 시간초과가 나고, pypy는 잘 돌아간다.

또한 이런 점화식을 사용할 때 배열의 인덱스를 위해 시작 인덱스를 1로 놓는데 이걸 깜박하고 누적합을 구할 때 0,0부터 돌려서 틀렸었다.

#사과나무, python 시간초과

import sys
n = int(sys.stdin.readline())
arr = []
for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))

#pre[i][j]=(0,0)~(i,j)까지의 합
pre = [[0]*(n+1) for _ in range(n+1)]
ans = -1000*300*300
for i in range(1,n+1):
    for j in range(1, n+1):
        pre[i][j] = pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1]+arr[i-1][j-1]
        if ans<arr[i-1][j-1]: ans = arr[i-1][j-1] #1X1 정사각형

#kXk크기의 정사각형
for k in range(2,n+1):
    for i in range(1,n-k+2):
        for j in range(1,n-k+2):
            #(i,j)~(i+k-1, j+k-1)까지의 합, kXk크기의 정사각형
            temp = pre[i+k-1][j+k-1]-pre[i+k-1][j-1]-pre[i-1][j+k-1]+pre[i-1][j-1]
            ans = max(temp, ans)
print(ans)