[백준][Python] 11660번 구간 합 구하기 5

11660번: 구간 합 구하기 5

코드

import sys
n, m = map(int,input().split())

n_list = [[0] * (n+1)]
for _ in range(n):
	a = [0] + list(map(int,sys.stdin.readline().split()))
	n_list.append(a)

for i in range(1,n+1): 
	for j in range(1,n+1):
		n_list[i][j] += n_list[i-1][j] + n_list[i][j-1] - n_list[i-1][j-1] 
		
		
for _ in range(m):
	x1,y1,x2,y2 = map(int,sys.stdin.readline().split())
	print(n_list[x2][y2]-n_list[x2][y1-1]-n_list[x1-1][y2]+n_list[x1-1][y1-1])

 

설명

누적합을 미리 구해놓았다.

예제1에서 (2,2)와 (3,4)까지의 합을 구해보면

 n_list[3][4]는 A+B+C+D를 의미한다. 따라서 해당하지 않는 부분인 A,B,C 부분을 빼줘야 한다.

n_list[x2][y1-1]이 A+C를 의미하고 n_list[x1-1][y2]가 A+B를 의미한다. A 부분을 두 번 빼줬으므로 n_list[x1-1][y1-1]을 다시 더해줘야 한다.