백준 11659번 구간 합 구하기 4: 누적 합을 한 번 만들어 두기

같은 합을 반복해서 구하지 않습니다

질문을 받을 때마다 구간의 원소를 모두 더하면 같은 값을 여러 번 계산하게 됩니다. 먼저 배열의 처음부터 각 위치까지의 합을 저장했습니다.

sum[0] = arr[0]으로 시작합니다. 그다음부터는 sum[i] = sum[i - 1] + arr[i]로 채웁니다. 이 배열을 한 번 만들면 각 질문의 답은 뺄셈으로 구할 수 있습니다.

입력으로 받은 양 끝 번호에서 1을 빼 배열 인덱스로 바꿉니다. 구간이 a부터 b까지라면 sum[b] - sum[a - 1]이고 a가 0이면 앞에서 뺄 부분이 없으므로 sum[b]를 그대로 사용합니다.

당시 제출 코드

Java

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

class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0 ; i < N ; i ++ ){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int[] sum = new int[N];
        for(int i = 0; i < N ; i ++){
            if( i == 0) sum[i] = arr[i];
            else sum[i] = sum[i-1] + arr[i];
        }
        int result = 0;
        for(int i = 0; i < M ; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken()) -1;
            int b = Integer.parseInt(st.nextToken()) -1;

            if(a == 0) result = sum[b];
            else result = sum[b] - sum[a-1];
            bw.write(result + "\n");
        }
        bw.flush();
    }
}