[백준] 11659. 구간 합 구하기 4

문제 링크

[백준] 11659. 구간 합 구하기 4

풀이 과정

N과 M이 최대 100,000 까지 가능하므로, 최악의 경우 $10^{10}$ 번의 탐색이 이루어지므로, 전부를 순회하는 방식의 풀이는 시간초과가 발생하게 됩니다. 따라서, 저는 왼쪽과 오른쪽 각각을 기준으로 시작되는 구간의 합을 미리 구해놓아 사용했습니다.

위 예제와 같이 입력을 받고 나면, 왼쪽부터 누적된 값을 요소로 갖는 배열 left 와 오른쪽부터 누적된 값을 요소로 갖는 배열 right 를 만들어 줍니다.

예를 들어, 구간 [2, 4] 의 합을 구하려고 한다면, 전체 구간 [1, 5]에서 [1, 2) 구간의 합과 (4, 5] 구간의 합을 빼주면 구할 수 있습니다.

왼쪽 노란색 구간의 총합은 left[1] 에 위치할 것이고, 오른쪽 주황색 구간의 총합은 right[5]에 위치할 것입니다.

따라서, 총 합에서 left[1] 과 right[5] 를 빼주면 구간 [2, 4] 의 합을 구할 수 있습니다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N + 1];
        int[] left = new int[N + 1];
        int[] right = new int[N + 1];
        int total = 0;

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

        int sum = 0;
        for (int i = 1; i <= N; i++) {
            sum += arr[i];
            left[i] = sum;
        }

        sum = 0;
        for (int i = N; i >= 1; i--) {
            sum += arr[i];
            right[i] = sum;
        }

        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int subsum = total;

            if (a - 1 >= 1) subsum -= left[a - 1];
            if (b + 1 <= N) subsum -= right[b + 1];

            answer.append(subsum + "\n");
        }

        System.out.println(answer);
    }
}