문제

https://www.acmicpc.net/problem/11659

설명

위 문제는 시간 제한이 1초이기 때문에 이중 포문을 사용하면 100억이 넘어가 100초가 되어서 다른 방법으로 문제를 해결해야 된다.
주인장은 구간 합을 이용하여 문제를 해결하려한다.

구간합

배열의 합을 구할때 시간 단축을 하기에 좋은 알고리즘 중 하나는 구간 합이다.

구간 합이란 합 배열을 이용하며 구간의 합을 구하는 알고리즘이다.

6칸이 있는 배열에 1부터 6까지 값을 들어 있는 배열 A가 있으면
새로운 배열을 만들어 인덱스 0번 A 배열부터 인덱스 5번 A배열까지의 각 합 들을 구해 새로운 배열 칸에 넣어 준다.

이렇게 합 배열이 구해지면 구간 합은 다음과 같이 이용하면 된다.

S[j] - s[i-1] // i에서 j까지의 합

이는 배열 A에서의 다음 상황과 같다.

구간의 합을 구할 시작 인덱스가 4이고 끝나는 값이 5인 경우

배열 A에서의 값은 5 + 6이며 이는 11의 결과값을 출력한다.

이를 합 배열로 구간 합을 구하면 다음과 같다.

0번 인덱스에서 5번 인덱스까지의 합 에서 0번 인덱스에서 3번 인덱스까지의 합을 빼주는 것이다. 그렇게 되면 결과값은 4번 인덱스 에서 5번 인덱스까지의 합만 남게 되는 것이다.

코딩

import java.util.Scanner;
public class J11659 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int index = scanner.nextInt();
        int n = scanner.nextInt();
        int[] array = new int[index];
        int[] array2 = new int[index+1];
        int sum = 0;
        int result = 0;
        for(int i = 0; i <array.length; i++) {
            array[i] = scanner.nextInt();
            sum += array[i];
            array2[i+1] = sum;
        }

        for(int i = 0; i < n; i++){
            int startNum = scanner.nextInt();
            int endNum = scanner.nextInt();
            result = array2[endNum] - array2[startNum-1];
            System.out.println(result);
        }

    }
}