[알고리즘] Java로 배우는 누적합/구간합 - feat.백준(구간합 구하기4)

특정 구간의 합을 여러 번 구해야 하는 문제를 풀 때, 단순하게 for문을 사용해서 매번 합을 구하면 시간 초과가 발생할 수 있다. 이런 경우에는 누적합(Prefix Sum)을 활용해서 빠르게 구간합을 구하는 방법을 사용한다.

 

누적합

누적합은 배열의 각 위치까지의 합을 미리 구해놓은 배열이다.

누적합 배열을 사용하면 어떤 구간의 합도 O(1)의 시간복잡도를 가진다.

 

예를 들어 배열이 [5, 4, 3, 2, 1]일 때, 누적합 배열을 만들면 다음과 같다.

(* 편한 계산을 위해 인덱스 0번은 비워두고 배열의 크기는 N+1로 한다.)

 

인덱스	1	2	3	4	5
원본 배열	5	4	3	2	1
누적합 배열	5	9	12	14	15

 

 

구간합

누적합 배열을 이용하면 i번째 수부터 j번째 수까지의 합은 다음 공식으로 구할 수 있다.

구간합(i, j) = S[j] - S[i-1]

• S[j] : 1번부터 j번까지의 합
• S[i-1] : 1번부터 (i-1)번까지의 합
• 따라서, 두 값을 빼주면 i부터 j까지의 합이 나온다.

💡 예를 들어 2~4 구간의 합을 구한다면,
S[4] - S[1] = 14 - 5= 9

 

 

 

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] prefixSum = new int[n + 1];
        for (int i = 1; i < prefixSum.length; i++) {
            int num = sc.nextInt();
            prefixSum[i] = num + prefixSum[i - 1];
        }

        for (int i = 0; i < m; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            int sum = prefixSum[end] - prefixSum[start - 1];
            System.out.println(sum);
        }
    }
}