[Java] 백준 11659 구간 합 구하기 4

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

제한
1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N

예제입력

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력

12
9
1

설명

길이 n의 배열을 m 횟수 만큼 더해서 값을 출력하는 문제이다.

예제를 그림으로 보자면

5에서 1까지의 배열이 있고
1번부터 3번까지의 숫자는 5,4,3이므로 더하면 12가 될 것이고,
2번부터 4번까지의 숫자는 4,3,2 이므로 더하면 9가 될 것이다.

이럴 때 합배열을 사용할 수 있다.

합배열이란 이전배열까지의 합을 저장해놓은 배열을 뜻한다.

예시의 배열을 합배열로 만들면 이렇게 된다.

합배열을 만드는 공식은 D[i] = D[i-1] + A[i] 이다

이게 무슨 말이냐면

5,4,3,2,1 배열이 있을 때
맨 처음
D[1] = D[1-1] + A[1] 은 = 0 + 5 = 5일 것이고,
두 번째
D[2] = D[2-1] + A[2] 는 (D의 1번째 인덱스 값(5)) 5 + 4 = 9 일 것이고,
세 번째
D[3] = D[3 -1] + A[3] 은 (D의 2번째 인덱스 값(9)) 9 + 3 = 12 일 것이고,
네 번째
D[4] = D[4 -1] + A[4] 는 (D의 3번째 인덱스 값(12)) 12 + 2 = 14 일 것이고,
마지막
D[5] = D[5 -1] + A[5] 는 (D의 4번째 인덱스 값(14)) 14 + 1 = 15 가 된다.

이렇게 합 배열을 만들어 놓고,

구간 합을 구하면 굉장히 간단하게 정답을 구할 수 있다.

구간 합을 구하는 공식은 D[j] - D[i -1] 이다.

예로들어서 1부터 3까지의 합을 출력하라고 했을 경우

합 배열에서 D[3] - D[1 -1] 은 12 - 0 = 0 이므로 답은 12가 된다.

2부터 4까지의 합을 출력한다면

합 배열에서 D[4] - D[2 -1] 은 14 - 5 = 9 이므로 답은 9가 된다.

이렇게 합 배열에서 구간 합을 구하는 공식이 D[j] - D[i -1] 인 이유는

1부터 3까지의 합이라고 했을 때

합 배열[j] 에는 1부터 3까지의 합이 들어있다. 그러니 [i] 에서 -1 을 해준 그 전 값을 빼면 그 사이의 합이 나오는 것이다.

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // int 수의 길이 변수 선언과 동시에 입력 받기
        int length = Integer.parseInt(st.nextToken());
        // int 합의 횟수 변수 선언과 동시에 입력 받기
        int sNum = Integer.parseInt(st.nextToken());
        // int[] arr 1차원 배열 선언
        long[] arr = new long[length + 1];
        st = new StringTokenizer(br.readLine());
        // for (수의 변수만큼 반복 ) {
        for (int i = 1; i <= length; i++) {
            int a = Integer.parseInt(st.nextToken());
            arr[i] = arr[i-1] + a;
        }
        // 합 배열 생성 d[i] = d[i-1] + a[i]
        // }
        for (int a = 0; a < sNum; a++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            // 구간 합 계산 d[j] - d[i-1]
            System.out.println(arr[j] - arr[i-1]);
        }
    }
}