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

문제 

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

11660번: 구간 합 구하기 5

---

아이디어

누적합을 이용해야 한다.

주어진 표에서 각 좌표별로 누적합을 계산한 뒤에 내가 구하고자 하는 좌표의 누적합을 구하면 된다. 

 

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

 

위의 표에서 각 위치별 누적합을 구해보자. 

 

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

 

우선 첫 번째로 (1, 2)의 2에 (1, 1)의 1을 더해주고, (2, 1)의 2도 (1, 1)의 1을 더해주면 된다.

그러면 다음과 같이 계산됨을 알 수 있다. 

 

1	3	3	4
3	3	4	5
3	4	5	6
4	5	6	7

 

이 과정까지는 쉽다. 그러면 (2, 2)의 경우 누적합은 어떻게 구하면 될까?

(2, 2)의 3에 (1, 2)까지의 누적합과 (2, 1)까지의 누적합을 더해주면 된다.

이 때, (1, 1)의 1은 (1, 2)까지의 누적합과 (2, 1)까지의 누적합을 계산하는 과정에서 중복되기때문에 빼줘야 한다.

 

1	3	3	4
3	8	4	5
3	4	5	6
4	5	6	7

 

즉, f(x, y)를 x, y지점의 누적합이라고 하면, 

$$f(x, y) = f(x-1, y) + f(x, y-1) - f(x-1, y-1) + arr[x][y]$$

이라는 것을 알 수 있다. 

 

(3, 3) 위치의 누적합을 계산하는 방법을 확인해보자. 

$$f(3, 3) = f(2, 3) + f(3, 2) - f(2, 2) + arr[3][3]$$이 된다. 

이다. 이 과정에서 인덱스 계산을 편하게 하기 위해서 다음과 같이 형태를 변형시켰다. 

이렇게 하면 arr[x]는 x번째 행이 된다. (그렇게 하지 않으면 arr[x]는 x+1번째 행이 된다.)

 

최종적으로 누적합으로 업데이트하면 다음의 결과를 얻을 수 있다. 

0	0	0	0	0
0	1	3	6	10
0	3	8	15	24
0	6	15	27	42
0	10	24	42	64

 (x1, y1)에서 (x2, y2)까지의 누적합을 구하고 싶으면, 

f(x2, y2) - f(x1-1, y2) - f(x2, y1-1) + f(x1-1, y1-1)을 구해주면 된다. 

---

Solution

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

graph = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(1, n+1) : 
    graph[i] = [0] + list(map(int, sys.stdin.readline().split())) 


for i in range(1, n+1) : 
    graph[1][i] += graph[1][i-1]
    graph[i][1] += graph[i-1][1]


for i in range(2, n+1) : 
    for j in range(2, n+1) : 
        graph[i][j] += graph[i][j-1] + graph[i-1][j] - graph[i-1][j-1]

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