[구간합, JAVA]백준 - 11659번

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

11659번: 구간 합 구하기 4

---

필자는 처음에 이 문제를 풀기 전에, 구간 합의 핵심 이론 부분의 합 배열 S를 만드는 공식이 이해가 되지 않았다. 
그래서 그냥 따라 치고 넘겼었는데, 이런 습관은 좋지 않은 습관이라고 피드백받아,
하나하나 분석하면서 다시 풀고 또 풀고 그랬었다. 그렇게 2번 정도 풀었을 때는 그 공식과 유사한 코드를 짰으며,
3번째에는 공식과 같은 코드를 짰다. 사실 공식이라기 보단 그냥 누적합 배열을 만드는 것이니까 공식의 형태로
적혀있는 것이다. 이게 무슨 말인지는 하나하나 분석을 하면 알 수 있다. 지금부터 그걸 알아보자.

우선 누적합이란 단어에 대해서 생각을 해봐야 한다.
예를 들어, 숫자가 [1, 2, 3, 4, 5]가 있으면 누적합은 [1, 1+2, 1+2+3,... , 1+2+3+4+5]
이런 식으로 하나씩 더해가는 합의 형태이다.

즉, 항이 하나씩 늘어날 때마다, 해당하는 항에 있는 숫자를 더하면 되는 것이다.

그러면 책에서 설명한 합 배열 공식의 원리를 우리는 지금 이해를 한 것이다.
합 배열을 S, 숫자 배열을 N이라고 둔다면, S[(현재 항)] = S[(이전 항)] + N[(현재항)] 이렇게 되는 것이다.

이 내용을 기억하고 문제를 봐보자.
문제에서 요구하는 것은 입력받는 첫번째 값부터 두 번째 값까지의 값을 요구하고 있다.
예제에 나온 것으로 예를 들자면, [5,4,3,2,1]의 누적합은 [5, 9, 12, 14, 15]이다.
여기에서 1항~3항까지의 합을 구한다고 생각을 해보면, 12가 그 답이 될 수 있을 것이다. 왜냐하면 1~3항을 누적해서 더한 게 12이기 때문이다.
그럼 2항~4항까지의 합을 구한다면 어떻게 해야 할까? 2번째 항에서 4번째 항까지 더한다고 하면 일단 1항~4번째 항까지 더한 것에서 1항의 값을 빼면 되므로, 14-5 = 9 이렇게 되는 것이다.
5항 ~ 5항까지의 합을 구한다면 마찬가지로 1번째 항에서 5번째 항까지 더한 것에서 4번째 항까지 더한 것을 빼면 되므로, 15-14=1 이렇게 되는 것이다.

그럼 문제가 생긴다.
첫 번째 항부터 더한 것과 최소 두 번째 항부터 더한 것을 구별을 해야 한다.
이 문제를 해결하기 위해서 책에서 소개하는 누적 합의 알고리즘은 [0, 5, 9, 12, 14, 15] 이렇게 되어있다.
즉, 1항~3항까지의 합을 구할 때에는 1항~3항까지 더한 값인 12에서 0을 빼는 것이다. 그럼 12일 테니까.

그럼 우리는 두 개의 패턴을 알아낼 수 있다.
첫 번째로 입력받는 항을 i라고 하고, 두 번째로 입력받는 항을 j라고 하자.
① S[(현재 항)] = S[(이전 항)] + N[(현재항)] = S[(현재항)] = S[(현재항 - 1)] + N[(현재항)]
② S[j] - S[i-1]

이전항이 왜 현재항 - 1이냐면, 이걸 인덱스로 생각했을 때,
예를 들어 2가 현재 항이라 가정하면, S[2] = S[1] + N[2] 이런 형식이기 때문이다.

그럼 이제 코드를 살펴보자.

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

public class BOJ_11659 {

	public static void main(String[] args) throws IOException{
		// TODO 백준 11659
		
        //입력을 빨리 받기 위해 BufferedReader 클래스를 이용함.
        //BufferedReader 클래스는 한 줄 단위로 입력을 받기 때문에
        //StringTokenizer 클래스로 문자열을 파싱해줘야 함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
        //N = 항의 개수
        //M = 문제에서 요구한 것들이 몇 개인지(질의가 몇 개인지)
        //sums = 누적합을 저장할 배열 변수
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken()); 
		long[] sums = new long[N+1];
		
        //누적합을 구하는 반복문
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			sums[i] = sums[i-1] + Integer.parseInt(st.nextToken());
		}
		
        //질의에서 요구하는 항들을 입력받고
        //합을 출력함
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int index1 = Integer.parseInt(st.nextToken());
			int index2 = Integer.parseInt(st.nextToken());
			
			System.out.println(sums[index2] - sums[index1-1]);
		}
	}
}