[백준] 17390 이건 꼭 풀어야 해! - 누적합(PrefixSum) JAVA

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

코드설명

누적합 문제입니다.

 

항상 누적합에서는 구간을 입력받는데, 이떄 범위를 잘 체크해야 합니다.

PrefixSum[N] : [0..N]까지의 합을 가진다. 

와 같이 정의합니다.

 

그렇다면, 만약 3부터 4까지의 합을 원한다면 어떻게 해야할까요?

prefixSum[4] - prefixSum[2] 로 처리해야 3과 4의 합이 나옵니다.

보시면, 4는 그대로 이지만 3은 -1 을 처리함을 알 수 있습니다.

 

문제에서 저는 prefixSum을 [0 .. N - 1]로 처리하였기에 문제에서는 [1..N]으로 처리하여 -1씩 왼쪽으로 이동시켜주어야 범위가 맞습니다. 

만약 1부터 10까지의 합이 들어왔다고 가정합니다.

그렇다면, prefixSum[10] - 0 의 값으로 구할 수 있습니다. 여기서 0 을 빼야하는 이유는 맨 첫번째 값을 뺴개 되면 arr[1]의 값이 제거되기에 2부터 10까지의 합으로 바뀌기 떄문입니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
    private static int N, M, Q;
    private static int[] arr;
    private static int answer = 0;
    private static int prefixSum[];
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		prefixSum = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		for(int i=0;i<N;i++) {
			prefixSum[i] = (i == 0) ? arr[i] : arr[i] + prefixSum[i-1];
		}
		
		for(int i=0;i<Q;i++) {
			st = new StringTokenizer(br.readLine());
			int L = Integer.parseInt(st.nextToken());
			int R = Integer.parseInt(st.nextToken());
			
			int LSum = (L - 1) == 0 ? 0 : prefixSum[L-2];
			int RSum = prefixSum[R - 1];
			System.out.println(RSum - LSum);
		}
		
    }
}