[백준] - 11660,python - 구간 합 구하기 5

https://www.acmicpc.net/problem/11660

 

아래 풀이는 "Do it 코딩테스트 파이썬 편" 이라는 책을 통해 배운 내용이다.

빨간부분의 합 - 파란부분 + 보라색부분 을 해주면 네모칸 안의 남은 값이 나온다. 

import sys
input = sys.stdin.readline

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

for i in range(n):
    tmp = [0] + [int(x) for x in input().split()]
    A.append(tmp)

for i in range(1,n+1): # 합 배열 구하기 
    for j in range(1,n+1):
        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

for _ in range(m): # 구간 합 구하기 
    x1,y1,x2,y2 = map(int,input().split())
    res = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
    print(res)