[BOJ 11659] 구간 합 구하기

 

구간 합이란 시간복잡도를 줄이기 위해 합 배열을 미리 생성하는 알고리즘이다.

기존 배결의 특정 범위의 합을 구하는 시간 복잡도는 O(N)이지만, 합 배열을 미리 구해 놓으면 시간 복잡도가 O(1)이 된다.

합 배열의 기본 공식은 S[i] = S[i - 1] + A[i]이다.

i에서 j까지의 구간 합 또한 S[j] - S[i - 1]로 나타낼 수 있다.

 

백준 11659. 구간 합 구하기 4
(시간 제한 0.5초)

 

< 문제 >

수 N개가 주어졌을 때, i번째 수에서 j번째 수의 합을 구하는 프로그램

 

< 입력 >

첫째 줄에 수의 개수 N(1 ≤ N ≤ 100,000)과 합을 구해야 하는 횟수 M(1 ≤ M ≤ 100,000)이 주어진다.

둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다.

셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

< 출력 >

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

// 예제 입력
5 3
5 4 3 2 1
1 3
2 4
5 5

// 예제 출력
12
9
1

 

 

< 풀이 >

문제에서 수의 개수와 합을 구해야 하는 횟수는 최대 100,000이다.

만약, 반복문을 사용하여 구간마다 합을 매번 계산한다면 시간 복잡도는 O(n)이 되며 0.5초 안에 모든 계산을 끝낼 수 없다.

합을 미리 구하여 합 배열을 만들어 두는 구간 합을 이용하면 시간 복잡도가 O(1)로 대폭 줄어든다.

 

배열 A의 수를 입력받음과 동시에 합 배열 S에 합을 저장한다.

인덱스	1	2	3	4	5
배열 A	5	4	3	2	1
합 배열 S	5	9	12	14	15

 

 

구간 i ~ j가 주어지면 구간 합 공식은 S[j] - S[i - 1]이 된다.

예를 들어, i = 2, j = 4가 주어지면 S[4] - S[1] = 14 - 5 = 9를 출력한다.

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st1 
        	= new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st1.nextToken());
        int M = Integer.parseInt(st1.nextToken());

        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        int[] A = new int[N + 1]; // 배열
        int[] S = new int[N + 1]; // 구간 합 배열

        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st2.nextToken());
            S[i] = S[i - 1] + A[i];
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer st3 = new StringTokenizer(br.readLine(), " ");
            sb.append(-S[Integer.parseInt(st3.nextToken()) - 1] 
            	+ S[Integer.parseInt(st3.nextToken())]).append("\n");
        }
        System.out.println(sb);
    }
}

• StringTokenizer의 nextToken()을 사용하면 앞에서부터 순서대로 값을 읽어올 수밖에 없다. 그래서 구간 합 공식인 S[j] - S[i - 1] 대신 -S[i - 1] + S[j]로 바꾸어 계산하였다.
  i와 j를 직접 변수로 저장하여 공식에 넣는 것이 덜 헷갈릴 수도 있겠다...!
• StringTokenizer를 처음으로 여러 개 써 보았다. st1, st2… 이렇게 이름만 바꾸어 주면 여러 개의 br.readLine()을 읽어올 수 있다.
• 배열을 선언할 때 길이를 N으로 설정하여 ‘ArrayIndexOutOfBoundsException’ 오류가 발생했었다. 공식에서 (i - 1)을 사용하기도 하고, ‘1번째 숫자 = 배열 1번’으로 통일하기 위해 배열 길이를 N + 1로 설정하여 오류를 해결했다.
• 여러 개의 결과를 출력할 때 StringBuilder의 append()를 이용해 값을 먼저 하나로 합친 뒤, 출력하는 방식을 이용하였다.
• 숫자가 클 경우에는 int보다는 long을 사용하는 것이 좋다