백준 11659번 ) 구간 합 구하기4 (java)

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

11659번: 구간 합 구하기 4

 

문제

 

풀이

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

public class BOJ_11659 {
    public static  void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] num = new int[N+1];
        num[0] = 0;
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1; i<N+1; i++){
            num[i] = num[i-1] + Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            System.out.println(num[end]-num[start-1]);
        }
    }
}

 

처음에 문제만 봤을 때는 단순히 배열에 저장하고, 저장한 배열에서 다 더해서 출력하려고 했다.

그러나 이런 문제는 누적합을 이용하는 문제로, 누적하여 더한 값을 저장 후 그만큼을 빼서 계산해야하는 문제이다.

그렇다면 굳이 입력된 수를 배열로 저장할 필요가 없으므로, 입력 받으면서 바로바로 누적합을 구해서 배열에 저장하고, 출력한다.

 

이때, num[end] - num[start-1] 이어야 함을 기억하자!