소스 코드

import sys
input = sys.stdin.readline

N = int(input().rstrip())
ground = [[0] * (N + 1)] +  [[0] + list(map(int, input().rstrip().split())) for _ in range(N)]
acc_sum = [[0] * (N + 1) for _ in range(N + 1)]

for row in range(1, N + 1):
    for col in range(1, N + 1):
        acc_sum[row][col] = ground[row][col] + acc_sum[row - 1][col] + acc_sum[row][col - 1] - acc_sum[row - 1][col - 1]

result = -sys.maxsize
for area in range(1, N + 1):
    for start_row in range(1, N - area + 2):
        for start_col in range(1, N - area + 2):
            end_row = start_row + area - 1
            end_col = start_col + area - 1

            area_sum = acc_sum[end_row][end_col] - acc_sum[start_row - 1][end_col] - acc_sum[end_row][start_col - 1] + acc_sum[start_row - 1][start_col - 1]
            result = max(result, area_sum)

print(result)

풀이

1. 2차원 누적 합을 구한다.

2. 가능한 모든 정사각형 area를 3중 for문으로 순회하면서, 각 정사각형의 합을 미리 구해둔 직사각형 누적 합을 이용하여 구해준다.

어려웠던 점, 배운 점

• 처음에 누적 합으로 풀고 냈더니 python3로는 TLE가 나고, pypy3로는 통과가 됐다. 그런데 다른 사람들의 python3 풀이를 보니 마찬가지로 누적합이었다. 무슨 차이인가 고민해보다가 혹시나 해서 누적 합 배열과 문제에서 주어진 배열의 인덱스를 1부터 시작되도록 조정을 해줬더니 python3에서도 통과가 됐다.

  일부러 인덱스 조정 안하고, 3중 for문 돌 때 인덱스 처리를 if문으로 적절히 처리해주는 식으로 구현했는데, 구현의 편리성도 그렇고 추가 연산 측면에서도 그렇고 인덱스를 조정해주는 쪽이 더 나은 방식인 것 같다. 앞으로는 이렇게 해야겠다.