[백준/Java] 11659 - 구간 합 구하기 4

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

문제

---

풀이

처음엔 배열을 stream()을 사용하여 구간 합을 구하면 될 것 같았는데 시간초과가 났다

누적합을 배열에 저장해두는 방식으로 진행하였다

1. 원본 배열 arr이 있다
2. 누적합을 저장할 배열 sum을 만든다. sum[i]는 0부터 arr[i]까지의 합이다
3. sum[0] = 0 으로 초기화하고 'sum[i] = sum[i - 1] + arr[i]'로 sum 배열을 완성한다
4. 인덱스 x부터 y까지의 합을 구하고 싶다면 sum[y] - sum[x - 1]을 계산하면 된다
   1. sum[y] = arr[0] + arr[1] + ... + arr[x - 1] + arr[x] + ... + arr[y]
   2. sum[x] = arr[0] + ... + arr[x]
   3. sum[y] - sum[x - 1] = arr[x] + ... + arr[y]

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

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

        long[] sum = new long[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            // sum[i] = sum[i - 1] + arr[i]
            sum[i] = sum[i - 1] + Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            long result = sum[y] - sum[x - 1];
            sb.append(result + "\n");
        }

        System.out.println(sb);

    }
}

결과