[백준]11659. 구간 합 구하기 4(Java, 자바)

문제

11659. 구간 합 구하기 4

📌 아이디어

누적합(Prefix Sum)

• 누적합이란 수열 An에 대해서 각 인덱스까지의 구간의 합을 구하는 것을 누적합이라고 합니다.
• 시작점은 항상 첫번째 원소이며, R번째 원소까지의 합을 앞에서부터 쭉 더해오는 패턴입니다.
• 모든 구간에 대해서 처음부터 계산하여 단순 반복하는 것이 아니라 이전 인덱스까지의 누적합에 현재 자기 자신 값을 더하여 구현하는 것이 효과적인 방법입니다.

예시 : [ 1, 2, 3, 4, 5 ] 로 이루어준 숫자 배열에서 각 구간까지의 합을 구하는 배열 [ 1, 3, 6, 10, 15] 을 구한다고 가정해보면 아래와 같이 2가지로 구할 수 있습니다.

[ 첫번째 방법 ]
1
1+2
1+2+3
1+2+3+4
1+2+3+4+5

[ 두번째 방법 ]
1
1+2
3+3
6+4
10+5

2가지 방법을 비교해보면 두 번째 방법이 훨씬 효율적이라는 것을 알 수 있습니다. 첫 번째 방법은 코드로 구현한다면 이중 for 문을 활용해 O(N^2)의 시간 복잡도를 가지지만, 두 번째 방법은 하나의 for 문으로 처리 가능하기 때문에 훨씬 효율적인 O(N)의 시간 복잡도를 가집니다.

구간합

구간합은 위에서 구한 누적합을 가지고 손쉽게 도출할 수 있습니다.

구간이 n ~ m 이라 가정했을 때, 누적합 배열 기준으로 prefixSum[m] - prefixSum[n-1]을 계산한다면 빠르게 구간합을 구할 수 있습니다.

📌 코드

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

public class BOJ_11659 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line1 = br.readLine();
        StringTokenizer st1 = new StringTokenizer(line1, " ");

        int n  = Integer.parseInt(st1.nextToken());
        int m = Integer.parseInt(st1.nextToken());
		
        // 누적합 구하기
        int[] prefixSum = new int[n+1];
        String line2 = br.readLine();
        StringTokenizer st2 = new StringTokenizer(line2, " ");
        for (int i = 1; i<=n; i++) {
            prefixSum[i] = prefixSum[i-1] + Integer.parseInt(st2.nextToken());
        }
		
        // 구간합 구하기
        for (int k = 0 ; k<m; k++) {
            String line3 = br.readLine();
            StringTokenizer st3 = new StringTokenizer(line3, " ");
            
            int i = Integer.parseInt(st3.nextToken());
            int j = Integer.parseInt(st3.nextToken());

            System.out.println(prefixSum[j] - prefixSum[i-1]);
        }
    }
}

피드백 및 개선점은 댓글을 통해 알려주세요😊