백준 / 11659번 / 구간 합 구하기 4 (prefix sum-누적합)
[문제]
수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
[출력]
총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.
[제한]
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 100,000
- 1 ≤ i ≤ j ≤ N
[예제 입력]
5 3
5 4 3 2 1
1 3
2 4
5 5[예제 출력]
12
9
1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N + 1];
int[] sumArr = new int[N + 1];
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i < N + 1; i++) {
arr[i] = Integer.parseInt(st2.nextToken());
sumArr[i] = sumArr[i - 1] + arr[i];
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
StringTokenizer st3 = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st3.nextToken());
int b = Integer.parseInt(st3.nextToken());
sb.append(sumArr[b] - sumArr[a - 1] + "\n");
}
System.out.println(sb);
}
}처음에 누적합이라는게 있는줄 모르고, 단순히 배열에 수를 저장한 후
i, j 값을 입력받아 그 부분을 더해줬는데, 당연히 시간초과가 떴다.
"누적합" 을 이용해서 푸는 문제여서, 우선 누적합에 대해 찾아봤다.
누적합
배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 경우 즉, 내가 시도했던 방법은 최악의 경우 O(N^2)의 시간복잡도를 갖기 때문에 입력 범위가 클 땐 사용할 수 없다.
하지만 prefix sum 방식을 사용하면 O(N)으로 해결이 가능하다.
예로, 크기가 5인 arr 배열에서 3~5 구간의 구간합을 구한다고 가정하면,
이 누적합은 arr[0~b] 의 누적합 - arr[0~a-1] 의 누적합 으로 표현할 수 있다.
각 인덱스 값에 해당되는 누적합을 저장한 것이다.
그리고, 3번~5번 구간 사이의 누적합을 구하려면
1번~5번까지의 누적합에서 1번~2번 구간의 누적합을 빼주면 된다!
그런식으로 이용하면,
위의 문제로 예를 들었을 때 길이가 5인 배열에 5 4 3 2 1 이 저장돼있고
1~3 구간의 누적합을 구하려면
1~5 구간의 누적합 - 1~2 구간의 누적합이 정답이 된다.
누적합에 대해 잘 몰라서 시간 초과가 뜬 문제인데, 알고보니 어렵지 않다.
다음에 까먹지 않으려면 누적합 관련 문제를 좀 더 풀어봐야 할 것 같다!