문제
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)까지 합을 구해 출력한다.
풀이
구간 합을 여러 번 물어보는 문제라서, 매번 직접 더하면 시간 내에 끝나기 어렵다. 그래서 먼저 누적합을 만들어 두고 각 질문을 상수 시간에 처리해야 한다.
현재 구현은 2차원 누적합을 사용한다. numbers[i][j]에 (1,1)부터 (i,j)까지의 합을 저장해 두면, 원하는 직사각형의 합은 포함과 제외를 한 번씩 적용해서 바로 꺼낼 수 있다.
쿼리마다 numbers[x2][y2] - numbers[x1 - 1][y2] - numbers[x2][y1 - 1] + numbers[x1 - 1][y1 - 1] 형태로 계산하는 부분이 핵심이다. 점화식과 쿼리 공식을 함께 기억하면 풀이가 깔끔하게 정리된다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] numbers = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++)
numbers[i][j] = numbers[i - 1][j] + numbers[i][j - 1] + Integer.parseInt(st.nextToken()) - numbers[i - 1][j - 1];
}
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
sb.append(numbers[x2][y2] - numbers[x1 - 1][y2] - numbers[x2][y1 - 1] + numbers[x1 - 1][y1 - 1]).append('\n');
}
System.out.println(sb);
}
}복잡도
- 시간 복잡도: 누적합 전처리와 개 질의를 처리하므로 이다.
- 공간 복잡도: 2차원 누적합 배열을 저장하므로 이다.
마무리
2차원 누적합 공식만 정확히 세우면 직사각형 합은 매번 다시 더할 필요가 없다.
