11659 구간 합 구하기 4 JAVA

이번 문제는 누적합을 이용하여 문제를 풀어야 한다.

누적합이란 한번에 입력값들의 합을 저장하고 필요한 부분만 골라 쓰는거 라고 생각하면 된다.

 

 

https://iamheesoo.github.io/blog/algo-boj11659

 

import java.util.Scanner;
public class S11659 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int N = sc.nextInt(), M = sc.nextInt();
        int[] numArr = new int[N];
        int[] preSum = new int[N+1];

        for(int i = 0; i < N; i++) {
            numArr[i] = sc.nextInt();
            preSum[i+1] = numArr[i] + preSum[i];
        }

        for(int i = 0; i < M; i++) {
            int j = sc.nextInt(), k = sc.nextInt();
            sb.append(preSum[k] - preSum[j-1] + "\n");
        }
        System.out.println(sb);
    }
}

 

예를 들어, 숫자 5,4,3,2,1을 입력했다면 각 preSum 배열의 요소엔 0,5,9,12,14,15로 저장이 될 것이다.

 

만약 첫번째 숫자와 3번째 숫자까지의 총합을 구하려면,  누적합이 저장되어 있는 배열에서

preSum[3] - preSum[1-1]을 하면 된다.1을 빼주는 이유는, preSum의 첫번째 요소에 5+4의 값이 저장되는 것이 아닌,

5 첫번째의 값이 저장되기에 1을 빼줘야 한다. 이해가 안간다면 노트에 적어서 스스로 빼보는것도 좋을 거 같다.