[JAVA] 백준 (실버3) 11659번 구간 합 구하기 4

링크

https://www.acmicpc.net/problem/11659

---

문제 설명

정답률 38.823%
수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

---

입력 예제

• 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다.
• 둘째 줄에는 N개의 수가 주어진다. (수는 1,000보다 작거나 같은 자연수이다.)
• 셋째 줄부터 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

---

출력 예제

• 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

12
9
1

---

풀이

구간 합(Prefix Sum)은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.

합 배열을 다음과 같이 정의할 때 합 배열은 기존의 배열을 전처리한 배열이다.
$S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]$
이렇게 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.

int[] A = {1, 2, 3, 4, 5}
int[] S = {1, 3, 6, 10, 15}

합 배열 없이 구간 합을 구하는 경우, 최악의 경우는 0부터 N까지의 합을 구하는 것으로 이때 시간 복잡도는 O(N)이다. 합 배열을 이용하면 O(1)으로 답을 구할 수 있다.

합 배열 S를 만드는 공식은 다음과 같다.
$S[i] = S[i-1] + A[i]$

구간 합을 구하는 공식은 다음과 같다.
$S[j] - S[i-1]$ (i에서 j까지의 구간 합)

이 문제의 경우 수의 개수와 합을 구하는 횟수는 최대 100,000으로 합 배열없이 구간마다 합을 계산하면 최악의 경우 100,000 * 100,000 번의 연산을 해야되므로 시간 초과가 난다. 합 배열을 이용하면 간단하게 해결할 수 있다.

코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        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[] sum = new int[N + 1];  //합 배열
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            sum[i] = sum[i - 1] + Integer.parseInt(st.nextToken());
        }

        for (int testCase = 0; testCase < M; testCase++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            //i번째 수부터 j번째 수까지의 합
            System.out.println(sum[j] - sum[i - 1]);
        }

    }
}