[백준] 11659번 - 구간 합 구하기 4

 

11659번: 구간 합 구하기 4

 

 

 

 

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지의 합을 구해야 한다.

 

 

 

 

 

 

조건

1 <= N <= 100,000

1 <= M <= 100,000 (M은 i ~ j 까지의 합을 구하는 횟수)

1 <= i <= j <= N

시간 제한 1초

 

 

 

 

 

 

풀이 방향

이 문제는 구간합을 맛볼 수 있는 문제이다. 먼저 구간합을 사용하지 않았을 경우 결과를 확인해보기 위해 완전탐색(브루트 포스) 풀이법을 시도해보았다. 결과는 시간 초과.

시간 초과의 원인을 찾아보자면 N과 M의 범위에 있다. 입력으로 주어지는 두 수의 최대값은 100,000이다. 만약 브루트 포스를 사용할 경우 최악의 경우 탐색해야 하는 횟수는 100,000 x 100,000 = 10,000,000,000 (100억)회 이다. 백준 자바 문제풀이 시 1억회 연산에 필요한 시간이 1초 정도라고 가늠한다는 글을 어디서 봤는데 이 계산법이 맞든 틀리든 100억번 연산은 1초라는 시간 제한에 턱없이 많은 횟수이다. 

따라서 완전 탐색보다 더 효율적인 알고리즘을 사용하여 연산 횟수를 줄여야 하는데, 특정 수열에서 연속적인 값들의 합의 최대/최소를 구하고자 할 때에는 누적 합을 적용하면 시간 복잡도를 선형 O(N)으로 줄일 수 있다. 

 

 

 

i 번째 수	5	4	3	2	1
누적 합	5	9	12	14	15

누적 합의 원리는 처음 N개의 수를 입력받을 때 누적 합을 저장하는데에 있다. 위 누적 합을 기록한 표를 토대로 예제에 주어진 (i, j) = (2, 4)의 경우를 확인해보겠다. 현재 4번 째 누적합에는 1, 2, 3, 4 네 수의 합을 저장하고 있다. 그리고 1번 째 누적 합에는 첫 번째 수만을 가지고 있다. 따라서 4번 째 누적 합에서 1번 째 누적합을 뺀 값은 2, 3, 4 세 수의 합과 같다. 

누적합을 이용하면 완전 탐색시 최악의 경우 100억 번의 연산이 필요한 것과 달리 최악의 경우에도 M의 최대인 100,000 번의 연산만 수행하면 된다.

 

 

 

 

 

 

전체 코드

import java.io.*;

public class Main {
    public static void main (String[] args) throws IOException {
        
// 입력 시작
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] input = br.readLine().split(" ");
        
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        
        int[] arr = new int[N+1];
        
        input = br.readLine().split(" ");
        for (int i=0; i<N; i++) 
        // 입력 받은 수를 그대로 저장하는 것이 아닌 누적 합을 저장한다. 
            arr[i+1] = arr[i] + Integer.parseInt(input[i]);
        
// 입력 끝
        
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<M; i++) {
            input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            
            // 누적 합을 저장한 배열에서 i번 째 부터 j번 째 까지의 구간 합은 arr[j]에서 arr[i-1]을 뺀 것과 같다.
            sb.append((arr[end] - arr[start-1]) + "\n");
        }
        
        System.out.println(sb);
        
        br.close();
    }
}