이 문제를 보면 어떻게 하면 정상적인 출력이 나오게끔 코드를 구현하는 것은 정말 쉬울 것이다. 하지만 !!! 그렇게 그 쉬운, 각 배열을 탐색해서 더하는 방법이라면 시간복잡도에 걸려서 시간초과라는 안타까운 결과를 보게된다.
문제 설명을 위한 예시를 보자,
숫자들로 채워진 N x N의 표가 있고, 두 개의 좌표 (x1, y1), (x2, y2)가 주어지면 (x1, y1)부터 (x2, y2)까지의 합을 구해야 한다. (x, y)는 x행 y열을 의미한다. 예를 들어 (2, 3)과 (4, 4)가 주어진 상황을 생각해보자. 2행 3열의 5와 4행 4열의 4를 양 끝으로 하는 직사각형에 포함된 수들의 합을 구해야 한다. 위 그림에서는 5+7+8+6+33+4=63이 될 것이다.
구간의 합 (prefix sum) 이란 ...? 구간 합은 어떤 수열에서 해당 인덱스까지의 수열의 전체 합을 의미한다.
예를 들어, [10, 20, 30, 40, 50]의 구간 합은 [10, 30, 60, 100, 150]이다. 위 문제는 구간 합을 2차원 배열에 적용하여 해결할 수 있다. 기본 구간 합이 수열의 처음 수부터 해당 인덱스의 수까지의 합을 저장한다면, 2차원 배열에서는 1행 1열부터 x행 y열까지의 수들의 합을 prefix_sum[x][y]에 저장할 수 있다.
예를 들어 위 그림의 구간 합을 만든다고 하면, prefix_sum[2][3]에는 1행 1열부터 2행 3열까지의 합을 저장하면 된다. 이 값은 1+2+3+1+3+5=15가 될 것이다.
1행부터 (x, y)까지의 합을 구하고 나면 (x1, y1)부터 (x2, y2)까지의 합을 구하기 쉬워진다.
(3, 3)부터 (4, 5)까지의 합을 구하는 예시를 생각해보자. 위 그림에서 구해야 할 값은 D에 속한 수들의 합이다. prefix_sum[4][5]은 A ~ D를 모두 더한 값과 같다. 여기에서 A, B, C의 값을 빼면 구하고자 하는 D의 값이 남는다. prefix_sum[2][5]는 A + B이고, prefix_sum[4][2]는 B + C이다. A ~ D의 합에서 이 둘을 빼면 D - A가 된다. A의 값은 prefix_sum[2][2]이므로 이 값을 더하면 구하고자 하는 D의 값이 된다.
2. 정답코드 Python
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
maps = []
maps.append([0] * (N + 1))
for i in range(N):
maps.append([0] + list(map(int, input().split())))
# 행의 합
for i in range(1, N + 1):
for j in range(N):
maps[i][j + 1] = maps[i][j] + maps[i][j + 1]
for j in range(1, N + 1):
for i in range(N):
maps[i + 1][j] = maps[i][j] + maps[i + 1][j]
for _ in range(M):
y1, x1, y2, x2 = map(int, input().split())
print(maps[y2][x2] - maps[y1 - 1][x2] - maps[y2][x1 - 1] + maps[y1 - 1][x1 - 1])
3. 정답코드 Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int y1, x1, y2, x2;
static int[][] maps;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
maps = new int[N + 1][N + 1];
for (int i = 1; i < N + 1; i ++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j < N + 1; j++) {
maps[i][j] = Integer.parseInt(st.nextToken());
}
}
// 행의 합
for (int i = 1; i < N + 1; i++) {
for (int j = 0; j < N; j++) {
maps[i][j + 1] = maps[i][j] + maps[i][j + 1];
}
}
// 열의 합
for (int j = 1; j < N + 1; j++) {
for (int i = 0; i < N; i++) {
maps[i + 1][j] = maps[i][j] + maps[i + 1][j];
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
y1 = Integer.parseInt(st.nextToken());
x1 = Integer.parseInt(st.nextToken());
y2 = Integer.parseInt(st.nextToken());
x2 = Integer.parseInt(st.nextToken());
System.out.println(maps[y2][x2] - maps[y1 - 1][x2] - maps[y2][x1 - 1] + maps[y1 - 1][x1 - 1]);
}
}
}
