BOJ 11659 구간 합 구하기 4 [Java]

BOJ 11659 구간 합 구하기 4

1. 문제 링크

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

2. 문제 해설

가장 쉽게 생각할 수 있는 방법은 그냥 더해주는 것이다. 근데 이 방법은 시간복잡도가 O(nxm)으로 굉장히 느리기 때문에 다른 방식을 생각해보자.
다른 방법으로는 구간합을 이용한 방법을 떠올릴 수 있다. 특정 구간까지의 합을 저장해둔 배열을 이용하는 방식이다.
sum[i]는 처음부터 i개의 원소를 합한 값이다. 즉, 0 ~ i-1 인덱스의 원소의 합을 뜻한다.
그러므로, sum[0]=0 이고, 수들을 입력 받으면서 나머지 sum 배열의 원소들도 채워준다.
구하고자 하는 값이 i번째 수부터 j번째 수의 합이라면 sum[j]-sum[i-1]의 값을 구해주면 O(1)으로 쉽게 구할 수 있다.

3. 코드 보기

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

public 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 = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        int[] pSum = new int[n + 1];
        pSum[0] = 0;

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

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            pSum[i + 1] = pSum[i] + arr[i];
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            sb.append(pSum[end] - pSum[start - 1] + "\n");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}