[백준/JAVA] 11659번 구간 합 구하기 4 - 구간 합(Prefix Sum)

풀이

구간 합을 미리 구한다.

일일이 구하게 되면 시간초과다.

sum[n] = sum[n-1] + arr[i]

를 통해 미리 값들을 구해둔다.

코드

제출 코드

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();
    }
}