백준 - 11659번(구간 합 구하기 4)

문제 출처: https://www.acmicpc.net/problem/11659

문제

• 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

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 {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken()); // 수의 개수
        int M = Integer.parseInt(tokenizer.nextToken()); // 합을 구해야 하는 횟수

        tokenizer = new StringTokenizer(reader.readLine());
        int[] nums = new int[N + 1];

        // 누적 합
        for (int i = 0; i < N; i++) {
            int temp = Integer.parseInt(tokenizer.nextToken());
            nums[i + 1] = nums[i] + temp;
        }

        for (int x = 0; x < M; x++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int i = Integer.parseInt(tokenizer.nextToken());
            int j = Integer.parseInt(tokenizer.nextToken());

            int sum = nums[j] - nums[i - 1];
            sb.append(sum).append("\n");
        }

        System.out.println(sb);
    }

}

• 처음에는 단순히 배열을 인덱스 범위 내를 탐색하며 답을 구하였으나 시간초과가 나왔다.
• 해결방법으로 누적 합을 이용하였다.
• i부터 j까지의 합을 구하려면 j까지의 누적 합에서 i - 1까지의 누적 합을 빼주면 값이 도출된다.