백준 11660 : 구간합 구하기 5 (Python)

본문 링크

import sys
input=sys.stdin.readline

N,M=map(int,input().split())

dp=[ [0]*(N+1) for i in range(N+1)]

L=[]
for i in range(N):
    L.append(list(map(int,input().split())))


for i in range(1,N+1):
    for j in range(1,N+1):
        dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+L[i-1][j-1]

for i in range(M):
    x1,y1,x2,y2=map(int,input().split())
    print(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1])

📌 어떻게 접근할 것인가?

처음엔 단순히 1차원 누적합처럼 풀었다가 틀렸다.

2차원적으로 누적합을 생각했을때

$dp$ 의 증가값은 $dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+L[i-1][j-1]$ 이고

$x1,y1$ 부터 $x2,y2$ 까지의 합은 $dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]$ 가 올바른 식이 된다.

왜냐하면 3번째 그림의 겹치는 부분이 생기기 때문이다.