자바 [Algorithm] 누적합 - 백준 11659 구간 합 구하기 4

1. 문제 

 

2. 접근법

입력

1번째 줄 : N, M

2번째 줄 : N+1 크기의 배열 값

3번째 줄 이후 : 1~3구간의 합, 2~4구간의 합, 5~5 구간의 합

 

누적합 알고리즘은 누적 합 배열을 만들고 원하는 구간의 값을 출력하는 것이 편하다.

 

[기본 배열]

0	1	2	3	4	5
0	5	4	3	2	1

 

[누적 합 배열]

0	1	2	3	4	5
0	5	9	12	14	15

 

1~3구간의 합은

5 + 4 + 3 = 12이다.

출력하기 위해서는 누적합 배열에서 [3] - [1-1] = 12 값을 출력

 

2~4 구간의 합은 

4 + 3 + 2 = 9이다.

출력하기 위해서는 누적합 배열에서 [4] - [2-1]  = 14 - 5 = 9 

 

따라서 i, j로 취급하여

누적합배열[i] - 누적합배열[j-1]을 하면 원하는 값이 나온다.

 

3. 코드

package week08;

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

public class Baek11659 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());

        int[] arr = new int[N+1];
        int[] prefix = new int[N+1];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for (int i = 1; i < N+1; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        for (int i = 1; i < N+1; i++) {
            prefix[i] = prefix[i-1] + arr[i];
        }

        while(M --> 0){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int x = Integer.parseInt(stringTokenizer.nextToken());
            int y = Integer.parseInt(stringTokenizer.nextToken());
            System.out.println(prefix[y] - prefix[x-1]);
        }

    }
}

 

4. 피드백

누적합 배열 구하는 코드를

for(int i=1; i<=N; i++){
    D[i] = D[i-1] + Integer.parseInt(stringTokenizer.nextToken());
}

 

이렇게 만들면 코드를 줄일 수 있다.