[BOJ] 11659번 구간 합 구하기 4

HSJ·2025년 3월 4일

1. 문제

문제

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

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

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

제한

1 ≤ N ≤ 100,000

1 ≤ M ≤ 100,000

1 ≤ i ≤ j ≤ N

2. 풀이

더 이상은 주먹구구식 해결 방법은 통하지 않는다.
그러므로 어떠한 방법이 필요한데 이 경우에는 누적합을 미리 구해놓는 방법이다.
누적합은

a = [ 1, 2, 3, 4, 5 ]

일 때

b = [ a[0], a[0] + a[1], a[0] + a[1] + a[2], a[0] + a[1] + a[2] + a[3], a[0] + a[1] + a[2] + a[3] + a[4] ]

를 미리 구해두는 방법이다.

이 방법을 이용하면 0부터 n까지의 합을 구할 수 있으며,
x부터 y까지의 합을 구하고자 한다면 b[y] - a[x - 1]라는 간단한 식으로 해결할 수 있기 때문이다.

원리는 간단한데
만약 2부터 4까지의 구간 합을 구하고 싶은 경우

b[4] = a[0] + a[1] + a[2] + a[3] + a[4]

b[1] = a[0] + a[1]

이므로 b[4]에서 b[1]을 빼게 되면

b[4] = ~~a[0] + a[1]~~ + a[2] + a[3] + a[4]
b[1] = ~~a[0] + a[1]~~

위와 같이 중첩되는 부분이 소거 되어 a[2] + a[3] + a[4]만 남게 되기 때문이다.

3. 문제 풀이

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

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

        StringTokenizer tok = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(tok.nextToken());
        int M = Integer.parseInt(tok.nextToken());
        int[] arr = new int[N];
        tok = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(tok.nextToken());
        }
        long[] sums = new long[N];
        long sum = 0;
        for (int i = 0; i < N; i++) {
            sum += arr[i];
            sums[i] = sum;
        }

        for (int i = 0; i < M; i++) {
            tok = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(tok.nextToken())-1;
            int b = Integer.parseInt(tok.nextToken())-1;
            if (a > 0)
                sum = sums[b] - sums[a - 1];
            else
                sum = sums[b];
            bw.write(sum + "\n");
        }

        bw.flush();
    }
}