백준[1749] 점수따먹기(파이썬)

2차원 배열에서 부분합에 대한 이해도를 묻는 문제.

행렬의 최대크기는 가로 x 세로 = 200 x 200 = 40000이며 O(n^2)이라고 하더라도 1억6천번으로 2초내에 계산이 가능하다.

특정 좌표 i, j에서 1, 1까지 부분합을 전부 계산하여 최대값이면 갱신하는 식으로 풀어냈다.

행렬의 크기를 1씩 늘려서 만들어주는 이유는 padding을 통해 계산을 용이하게 하기 위함이다.

n, m = map(int, input().split())
data = [[0] * (m+1) for _ in range(n+1)]

#부분합 만들어주기
for i in range(1, n+1):
    line = list(map(int, input().split()))
    for j in range(1, m+1):
        data[i][j] = line[j-1] + data[i-1][j] + data[i][j-1] - data[i-1][j-1]

#최대값 찾기
maxx = float('-inf')
for i in range(1, n+1):
    for j in range(1, m+1):
        for x in range(i, 0, -1):
            for y in range(j, 0, -1):
                maxx = max(maxx, data[i][j] + data[x-1][y-1] - data[i][y-1] - data[x-1][j])
print(maxx)