백준|11659번|구간 합 구하기4

문제설명
숫자들과 구간을 입력받아서 그 구간의 합을 출력하는 문제입니다.

작동 순서
1. 입력받을 숫자의 개수와 테스트케이스의 개수를 입력받습니다.
2. 입력받는 숫자들을 누적합형식으로 배열에 저장합니다.(배열 저장값=이전 배열의 저장값+현재 입력값)
3. 합을 구할 구간을 입력받습니다.
4. 구간의 끝자리 j까지의 합(누적합 배열의 j번째 원소)에서 구간의 첫자리 i 이전 까지의 합(누적합 배열의 i-1번째원소)를 빼줍니다.
5. 입력받은 구간의 합을 출력합니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 백준_11659번_구간합구하기4 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        String[] input = br.readLine().split(" ");
        int N=Integer.parseInt(input[0]);
        int M=Integer.parseInt(input[1]);
        int[] cumulativeSum=new int[N+1];
        input=br.readLine().split(" ");
        for(int i=0;i<N;i++) cumulativeSum[i+1]=Integer.parseInt(input[i])+cumulativeSum[i];

        for(int i=0;i<M;i++){
            input=br.readLine().split(" ");;
            sb.append(cumulativeSum[Integer.parseInt(input[1])]-cumulativeSum[Integer.parseInt(input[0])-1]+"\n");
        }
        System.out.print(sb);
    }
}

후기
처음에 배열에 숫자들을 입력받고 구간을 입력받을 때 마다 숫자들을 더해서 합을 구했었는데 그렇게 하니까 시간초과가 나오더군요. 그래서 문제 질문에 있는 누적합이라는 키워드를 보고나서는 굉장히 쉽게 풀 수 있었습니다. 많은 정보와 유형을 아는 것이 중요한 것 같습니다.