문제 설명

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

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

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

풀이 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import sys

n, m = map(int, sys.stdin.readline().split())


points = []
for _ in range(n):
    temp_list = list(map(int, sys.stdin.readline().split()))
    points.append(temp_list)

    # n x n 각 point에 1,1~ i, j 누적합을 계산한다
    # x1, y1 -> x2, y2 계산은 (x1-1, n) + (n, y1-1)-(x1-1, y1-1)

sums = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        sum = points[i][j]

        sum = sum + sums[i - 1][j] if i >= 1 else sum
        sum = sum + sums[i][j - 1] if j >= 1 else sum
        sum = sum - sums[i - 1][j - 1] if i >= 1 and j >= 1 else sum

        sums[i][j] = sum


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

    if x1 == 1 and y1 > 1:
        result = result - sums[x2 - 1][y1 - 2]
    elif y1 == 1 and x1 > 1:
        result = result - sums[x1 - 2][y2 - 1]
    elif x1 > 1 and y1 > 1:
        result = (
            result - sums[x2 - 1][y1 - 2] - sums[x1 - 2][y2 - 1] + sums[x1 - 2][y1 - 2]
        )

    print(result)

CHECK!

DP로 풀려면 어떻게 해야하지 고민하다가, NxN 표 각각에 대해 (1,1)부터 누적합을 구하고, 그 사이 구간합을 누적합을 통해 계산하는 방식으로 진행했다.
누적 합(prefix sum)과 구간 합에 대한 설명을 찾아본 후에 문제를 다시 풀면 좋을 것 같다.