[P&B] #117 BAEKJOON 11659

백준 11659번 JAVA 구간 합 구하기 4

문제 설명

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

 

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

나의 문제 풀이 코드

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

public class bj11659 {
    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());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int[] prefix_sum = new int[N+1];
        for (int i = 1; i <= N; i++) {
            prefix_sum[i] = prefix_sum[i-1]+Integer.parseInt(st2.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        for (int k = 0; k < M; k++) {
            StringTokenizer st3 = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st3.nextToken());
            int j = Integer.parseInt(st3.nextToken());
            sb.append(prefix_sum[j]-prefix_sum[i-1]).append("\n");
        }

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

 

문제 풀이 코멘트

 구간 합이라는 것만 보고 처음에는 구간의 리스트를 따로 서브리스트로 구해 합을 구하는 방식으로 풀려고 했으나 시간복잡도가 크게 나왔습니다. 그래서 누적 합이라는 개념을 적용해 보았습니다.

 누적 합의 개념은 어렵지 않습니다.

1. 입력받은 숫자의 갯수보다 하나 더 큰 배열을 생성하여 각 인덱스에 n개의 누적 합을 저장해 주는 것입니다. 누접 합은 변하지 않으므로 한 번만 계산해놓고 필요한 부분을 뽑아서 씁니다.
2. 그래서 숫자를 입력받음과 동시에 이전 인덱스의 합과 더하여 n까지의 누적합을 구해 저장합니다.
3. 누적합 배열을 모두 구하면 array[j]-array[i-1]을 리턴하는 방식을 사용하면 됩니다.

누적 합 계산은 한번만 하기 때문에 어떤 인덱스 값을 입력받든 불필요한 시간 복잡도가 소요되지 않습니다.