BOJ11659 구간 합 구하기 4

https://www.acmicpc.net/problem/11659 (opens new window)

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구한다. N과 M의 크기가 최대 100,000이기 때문에 O(N^2)로 해결할 경우 시간 초과를 유발한다. 즉 단순 반복문을 활용할 수 없다.

누적합

누적합 (Prefix Sum, Cumulative Sum) (opens new window)

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ11659 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 배열의 개수
        int m = scanner.nextInt(); // 합을 구해야 하는 횟수

        int[] array = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            array[i] = array[i - 1] + scanner.nextInt();
        }

        while (m-- > 0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            System.out.println(array[b] - array[a - 1]);
        }
    }
}

#BOJ #누적합