Prefix Sum / 정수 n개의 합

*본 문제는 저작권자 © 브랜치앤바운드 의 저작권법의 보호를 받습니다. 

 

[문제]

1이상 100이하의 숫자로만 이루어진 n * n 크기의 2차원 격자 상태가 주어졌을 때, k * k 크기의 정사각형이 격자를 벗어나지 않게 잡았을 때 정사각형 내 숫자들의 합이 최대가 되도록 하는 프로그램을 작성해보세요.

 

[예제]

3 1
1 2 3
9 8 8
6 8 8

---

[풀이]

 

누적합 배열 공식

 

누적합을 배열로 먼저 구성한 다음, 문제를 진행한다.

이때, 누적합은 *누적합 배열 공식 을 참고한다.​​

import sys

n, k = map(int,input().split())

arr = []
s = []
arr.append([0]*(n+1))
ans = -sys.maxsize

for _ in range(n):
    arr.append([0] + list(map(int,input().split())))
    
for _ in range(n+1):
    s.append([0]*(n+1))

#누적합 배열 넣어주기 
for i in range(1,n+1):
    for j in range(1,n+1):
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + arr[i][j]

def sumcheck(x1,y1,x2,y2):
    return s[x2][y2] - s[x1-1][y2] -s[x2][y1-1] + s[x1-1][y1-1]

s[0][0] = 0

for i in range(1,n-k+2):
    for j in range(1,n-k+2):
        ans = max(ans, sumcheck(i,j,i+k-1,j+k-1))


print(ans)