직사각형의 합

문제

N x M 의 직사각형이 주어지며, 각 칸에는 정수가 들어있다. 이제 Q개의 질문에 대하여 답을 해야 하며, 각각의 질문은 (a, b)부터 (c, d)까지의 직사각형에 들어있는 정수의 합을 묻는다. 예를 들어, 다음과 같이 5 x 5 의 직사각형이 주어질 때, (1, 2) 부터 (3, 3) 까지의 직사각형에 들어있는 정수의 합은 26 이다.

 

입력

첫 번째 줄에 N, M, Q가 주어진다. ( 1 ≤ N, M ≤ 1,000, 1 ≤ Q ≤ 1,000,000 ) 두 번째 줄부터 N x M 직사각형이 주어진다. 직사각형 안의 숫자 S는 -100이상 100이하이다. 그 후 Q개의 질문이 주어진다. 각각의 질문은 “a b c d” 로 이루어 져 있으며, 이는 (a, b) 부터 (c, d) 까지의 직사각형에 들어있는 정수의 합을 묻는다. (0 ≤ a ≤ c < N, 0 ≤ b ≤ d < M)  

출력

각 질문에 대한 답을 출력한다.

 

예제 입력

5 5 3
 1 -2 3 2 8
-8 -9 3 4 5
 2 4 7 8 2
 1 4 3 1 4
-1 2 5 -6 3
1 2 3 4
0 0 1 1
2 0 2 1

예제 출력

37
-18
6

 

 

# 접근법

# 우선 주어진 입력값이 1 ≤ N, M ≤ 1,000, 1 ≤ Q ≤ 1,000,000 매우 크다 즉 직접 완탐으로는 시간초과가 난다.

# 메모이제이션 기법을 사용하여 시간복잡도를 줄인다.

# 1. 각 인덱스 위치에서의 합의 값을 가진다. 예 (1, 1) -> 1 -2 -9 -8 = -18

# 여기서 중요한 점은 -18 이라는 값을 점화식으로 도출해내야 한다는 것이다.

# (1,1)의 -18이라는 뜻은 (0, 0)에서 (1, 1)까지의 범위에 해당하는 값들의 합을 의미한다.

# 그래서 (1, 1)의 값은 dp_table 에서의 (주황부분 + 파랑부분 - 빨간부분) 그리고 원본 배열에서의 (1, 1)위치의 값을 더해준 값이다.

# dp_table[i][j] = dp_table[i-1][j] + dp_table[i][j-1] + arr[i-1][j-1] - dp_table[i-1][j-1]

# 코드를 살펴보면 위와 같다

# 만약 dp_table[0][0] 을 찾고자한다면 dp_table[-1][-1] 이런 값들이 나오게 되므로 인덱스 범위를 벗어나므로 

# dp_table2와 같이 위와 좌측을 0의 값을 가진 바리게이트? 역할을 하도록하는 행과 열을 추가할 것이다.

 

원본 배열

1	-2	3	2	8
-8	-9	3	4	5
2	4	7	8	2
1	4	3	1	4
-1	2	5	-6	3

 

합의 값을 저장한 dp_table

1	-1	2	4	12
-7	-18	-12	-6	7
-5	-12	1	15	30
-4	-7	9	24	43
-5	-6	15	24	46

안전장치를 넣어둔 dp_table2

0	0	0	0	0	0
0	1	-1	2	4	12
0	-7	-18	-12	-6	7
0	-5	-12	1	15	30
0	-4	-7	9	24	43
0	-5	-6	15	24	46

 

# 여기까지 왔다면 그래서 답은 어떻게 도출되는가? 에 대해 의문이 생길 것이다.

# 사실 위에서의 원리를 잘 이해 했다면 조금만 생각해본다면 유추해낼 수 있을 것이다.

# 첫 번째 케이스인 (1 2) (3 4) 를 예로 들어보자 

# dp_table2 를 보면 위와 좌측에 한줄씩 추가하였으니 좌표 또한 +1 해줘야 할 것이다.

# (2, 3)(4, 5)

# 영역으로 보면 우리가 원하는 것은 초록색 영역의 합니다. 하지만 46은 시작점을 (0, 0)을 기준으로 계산한 결과이다.

# 전체영역(43) - 보라색영역(-7) - 마젠타색영역(12) + 중복으로 계산되어 두 번 빼버린 회색영역(-1) 으로 계산해주면 된다.

 

 

 

#코드

import sys
  
if __name__ == "__main__":
  input = sys.stdin.readline
  n, m, q  = map(int, input().split())
  arr      = [list(map(int, input().split())) for _ in range(n)]
  dp_table = [[0]*(m+1) for _ in range(n+1)]
  
  for i in range(1,n+1):
    for j in range(1, m+1):
      dp_table[i][j] = dp_table[i-1][j] + dp_table[i][j-1] + arr[i-1][j-1] - dp_table[i-1][j-1]
 
  for _ in range(q):
    y1, x1, y2, x2 = map(int, input().split())
    
    y1+=1
    x1+=1
    y2+=1
    x2+=1
    res_val = dp_table[y2][x2] - dp_table[y2][x1-1] - dp_table[y1-1][x2] + dp_table[y1-1][x1-1]
    print(res_val)