문제
N개의 수가 주어졌을 때, i번째 수부터 j번째 수까지의 합을 구하는 쿼리 M개를 처리하는 문제다. 단순 반복으로 풀면 쿼리당 O(N)이 되어 시간 초과가 발생하므로 누적 합(prefix sum)을 사용해야 한다.
입력
- 첫째 줄: 수의 개수 N (1 이상 100,000 이하), 쿼리 수 M (1 이상 100,000 이하)
- 둘째 줄: N개의 정수 (각 1,000 이하의 자연수)
- 셋째 줄부터 M개 줄: 구간 쿼리 i j
출력
M개의 줄에 i번째 수부터 j번째 수까지의 합을 순서대로 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 3 5 4 3 2 1 1 3 2 4 5 5 | 12 9 1 |
풀이
누적 합 배열을 미리 구성하여 각 구간 쿼리를 O(1)에 처리한다.
- 1-인덱스 기반 누적 합 배열
arr[N+1]을 선언한다. arr[n] = arr[n-1] + 현재값으로 누적 합을 저장한다.- 구간
[i, j]의 합은arr[j] - arr[i-1]로 O(1)에 계산한다. StringBuilder로 출력을 모아 한 번에 출력해 I/O 성능을 높인다.
핵심 아이디어: 누적 합 배열을 1-인덱스로 구성하면 arr[j] - arr[i-1] 공식이 경계 조건 없이 균일하게 적용된다. 전처리 비용은 O(N)이고 이후 쿼리 하나당 O(1)이므로 전체 복잡도는 O(N + M)이다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day26BOJ11659구간합누적합 { // 11659 구간 합 구하기 누적합 안쓰면 시간초과
public static void main(String[] args) throws Exception {
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());
st = new StringTokenizer(br.readLine());
int[] arr = new int[N + 1];
for (int n = 1; n <= N; n++) {
arr[n] = arr[n - 1] + Integer.parseInt(st.nextToken());
}
for (int m = 0; m < M; m++) {
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
sb.append(arr[n2] - arr[n1 - 1]).append("\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N + M) — 누적 합 배열 구성 O(N), 쿼리 처리 O(M)
- 공간: O(N) — 누적 합 배열