[Algorithm][부분 합] 백준 11659 - 구간 합 구하기 4

알고리즘 분류

 부분 합

 

시간 복잡도

 \( O(n) \)

 

문제 링크

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

---

 

 해당 문제는 부분 합 알고리즘의 가장 기본적인 문제입니다. 부분 합 알고리즘의 핵심은 "처음부터 \( i \)번째까지 원소의 합을 미리 구해놓자"입니다. 그래서 특정 구간의 합을  \( O(1) \)의 시간으로 알아낼 수 있습니다.

 

 단순하게 for문을 이용하여 특정 구간의 합을 구하는 시간은  \( O(n) \)이지만 구간의 합들 중 가장 크거나 작은 값을 알려면 모든 구간의 합을 알아야 합니다. 그래서 결국 시간 복잡도는  \( O(n^2) \)가 됩니다. 이런 문제의 경우 \( N \)의 값은 10만 이상의 값이므로  \( O(n^2) \)의 시간 복잡도에서는 당연히 시간 초과가 납니다. 그래서 꼭 부분 합 알고리즘이 필요한 문제입니다.

 

풀이를 하자면 \( N \) 크기의 배열과 \( N+1 \) 크기의 배열을 만듭니다. 이 때 \( N+1 \) 크기의 배열은 구간의 합을 나타내며 \( i \)번째 인덱스의 값은 0부터 \( i-1 \)까지 원소들의 합을 나타냅니다 ( 0번째 원소는 0의 값을 가짐 ). 아래 예시를 보겠습니다. { 4, 3, 1, 2, 6 } 원소를 가지는 배열이 있다고 가정한다면 구간의 합을 저장하는 배열 Sum_Array의 값은 아래와 같습니다.

 

 

 좀 더 부연 설명을 하자면 Sum_Array의 \( i \)번째 값은 0부터 \( i-1 \) 까지 원소들의 합이므로 Sum_Array[2] 는 Array[0] + Array[1]의 값을 가집니다. 하지만 실제로 값을 저장할 때는 처음부터 저장하면 \( O(n) \)의 시간이 걸리므로 Sum_Array[\( i+1 \)] = Sum_Array[\( i \)] + Array[\( i \)]으로 구할 수 있습니다. 이러면 반복문이 필요 없는 단순 덧셈이므로 \( O(1) \)의 시간이 걸립니다.

 

 Sum_Array 배열의 값을 모두 구해놨다면 이제 어떠한 구간이 주어지더라도 \( O(1) \) 시간에 알 수 있습니다. 1부터 3까지 구간의 합을 구하고 싶다면 우리는 Sum_Array[4] - Sum_Array[1] 을 계산함으로써 빠르게 알 수 있습니다. 아래의 예시에서는 (10 - 4)의 결과인 6입니다.

Java

import java.util.*;

public class Main {

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

        int arr[] = new int[n];
        int sum_arr[] = new int[n+1];

        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
            sum_arr[i+1] += sum_arr[i] + arr[i];
        }

        for(int i=0; i<m; i++){
            int s = sc.nextInt();
            int e = sc.nextInt();

            System.out.println(sum_arr[e] - sum_arr[s-1]);
        }
    }
}