문제
N개의 수가 주어지고, M개의 질의 (i, j)에 대해 i번째부터 j번째 수까지의 합을 구하는 문제다. 매 질의마다 합산하면 O(NM)이므로 누적 합 전처리가 필요하다.
입력
- 첫째 줄: N
- 둘째 줄: N개의 수
- 셋째 줄: M
- 이후 M개 줄: i, j
출력
각 질의의 구간 합
예제
| 입력 | 출력 |
|---|---|
5 5 4 3 2 1 3 1 3 2 4 5 5 | 12 9 1 |
풀이
누적 합 배열 prefix를 미리 계산해두면, 임의 구간 [i, j]의 합을 prefix[j] - prefix[i-1]로 O(1)에 구할 수 있다.
- 수를 읽으면서 누적 합을
arr[1..N]에 저장한다 (arr[k] = arr[k-1] + 현재값). - M개의 질의를 읽으며 각
(i, j)에 대해arr[j] - arr[i-1]을 계산한다. - 결과를 StringBuilder에 모아 한 번에 출력한다.
핵심 아이디어: prefix[j] - prefix[i-1]로 구간 합을 O(1)에 처리한다. 사전에 O(N) 전처리를 하면 M개의 질의를 O(M)에 모두 처리할 수 있어 전체 시간 복잡도가 O(N+M)이 된다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day31BOJ11441합구하기부분합쓰면좋음 { // 11441 합 구하기
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
int[] arr = new int[N + 1];
int tmp = 0;
int idx = 0;
while (st.hasMoreTokens()) {
tmp += Integer.parseInt(st.nextToken());
arr[++idx] = tmp;
}
int M = Integer.parseInt(br.readLine());
for (int n = 0; n < M; n++) {
st = new StringTokenizer(br.readLine());
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());
sb.append(arr[j] - arr[i - 1]).append("\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N + M)
- 공간: O(N)