[Java] 백준 11659번 : 구간 합 구하기 4

문제

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

접근 방법

1. 구간 합을 구하는 문제는 브루트포스로 풀 수 있지만 이럴경우 구간마다 계속 더하는 걸 반복해야한다.
2. 따라서 구간합을 점과 점의 관계로 나타낼 수 있는 누적합배열을 만들어 풀어준다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N,M;
    private static int[]arr, prefix;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N+1];
        prefix = new int[N+1];

        st = new StringTokenizer(br.readLine());
        for(int i = 1 ; i <= N ; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            //누적합 배열 만들기
            prefix[i] = prefix[i-1]+arr[i];
        }

        for(int tc = 0 ; tc < M ; tc++){
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            process(i,j);
        }

    }

    //실행
    public static void process(int i, int j) {
        //구간과 구간을 점과 점으로 나타낸다.
        sb.append(prefix[j]-prefix[i-1]).append("\n");
    }


    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
}