[JAVA] 구간 합 구하기 (백준 11659번, 백준 2042번)

구간 합

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

 

어떠한 배열이 있을 때, 그 배열 중 특정 범위에 있는 원소 값들의 합을 구간 합 알고리즘으로 쉽게 구할 수 있습니다.

이 알고리즘을 활용하려면 합 배열을 알아야 합니다. 

 

합 배열 S의 정의

배열 A가 있을 때 합 배열 S는 다음과 같이 정의합니다.

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합

 

S[4]는 A[0]부터 A[4]까지 더한 합인거죠.

합 배열은 기존의 배열을 전처리한 배열입니다. 이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소합니다.

 

위 그림에서 S[4] = A[0] + A[1] + A[2] + A[3] + A[4] = 15 + 13 + 10 + 7 + 3 =48입니다.

 

합 배열에 S의 각 원소를 구할 때 매번 다시 A[0] + ... A[i]를 하기보다는 쉬운 방법이 있습니다.

바로 이전에 구한 S[i-1]에 A[i]를 더하는 거죠.

 

📌 합 배열 공식

S[i] = S[i-1] + A[i]

 

아래 그림에서 S를 차례대로 구해보면 쉽게 이해가 갈 겁니다.

 

이렇게 0번째 인덱스부터 어느 인덱스까지의 합은 합 배열로 구할 수 있습니다.

그렇다면 0번째가 아닌 i부터 j까지의 구간 합은 어떻게 구할 수 있을까요?

 

합 배열을 이용하면 됩니다.

📌 구간 합을 구하는 공식

S[j] - S[i-1] // i에서 j까지 구간 합

 

  A[2]부터 A[4]까지의 합을 구하고 싶다면, S[4] - S[1] = 28 - 9 = 19라고 구할 수 있다.

 

이제 이걸 이용해 백준 문제를 풀어보자.

 

11659번

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

• 입력: 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다.수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 구해진다.
• 출력: 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

import java.util.*;

class Main {
 public static void main(String[] args) {
  Scanner s = new Scanner(System.in);
  
  int N = s.nextInt();
  int M = s.nextInt();
  // 구간 합 구하기
  int[] sum = new int[N + 1];
  for (int i = 1; i <= N; i++) {
            sum[i] = sum[i - 1] + s.nextInt(); // 누적합
        }
 
  // M번 동안 입력 받는 동안 출력하기
  for (int m = 0; m < M; m++) {
            int i = s.nextInt();
            int j = s.nextInt();
            System.out.println(sum[j] - sum[i - 1]);
        }
 }
}

 

 

BufferReader와 StringTokenizer를 이용해 더 빨리 구할 수도 있습니다.

이건 하루코딩님의 코드입니다.

import java.io.*;

class Main {
	public static void main(String[] args) throws IoException {
    	BufferedReader bufferedReader = new BufferdReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        
        int N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());
        
        long[] s = new long[N+1];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for(int i=1;i<N+1;i++) { 
         s[i] = s[i-1] + Integer.parseInt(stringTokenizer.nextToken());
        }
        
        for(int m=0;m<M;m++) {
        	stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int i = Integer.parseInt(stringTokenizer.nextToken());
            int j = Integer.parseInt(stringTokenizer.nextToken());
            System.out.println(s[j]-s[i-1]);
        }
    }
}

 

하루코딩님의 "Do it! 알고리즘 코딩 테스트JAVA편 강의 내용입니다.