(Java) 누적 합 (feat. 백준 11660 구간 합 구하기 5)

누적합

누적합의 예제부터 살펴보자

 

[1, 2, 3, 4, 5] 배열이 있다고 할 때 각 구간까지의 합을 구하는 배열 [1, 3, 6, 10, 15]를 구한다고 가정해보면 두 가지 방법을 생각해볼 수 있다.

 

1. 완전 탐색으로 더하기

1
1+2
1+2+3
1+2+3+4
1+2+3+4+5

 

2. 누적합을 이용한 더하기

1
1+2
3+3
6+4
10+5

 

2가지 방법을 비교하면 2번째 방법이 효율적임을 알 수 있다.

 

누적합은 이처럼 시작점부터 n번째 원소까지 앞에서부터 누적으로 합해오는 알고리즘이다.

모든 구간을 반복해서 더하는 것보다 이전 인덱스까지의 누적합에 현재 인덱스를 더하여 구현하는 것이 효과적인 방법이다. 큰 계산을 작게 효율적으로 만든다는 점에서 DP와도 상통하는 부분이 있다.

누적합 알고리즘은 A~B 범위의 구간 합을 구하려고 할 때 유용하게 쓰인다.

B까지의 누적합에서 A-1까지의 누적합을 빼주면 간단하게 구할 수 있다.

 

 

 

구간 합 구하기 5 (백준 11660)

https://www.acmicpc.net/problem/11660

N * N 크기의 표가 주어지고 (x1, y1)부터 (x2, y2)까지의 합을 구하는 문제이다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int NArr[][] = new int[N+1][N+1];
        int M = Integer.parseInt(st.nextToken());

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

        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            int sum = 0;
            for(int j = x1; j <= x2; j++) {
                sum += NArr[j][y2] - NArr[j][y1-1];
            }
            sb.append(sum + "\n");
        }

        System.out.println(sb);
    }
}

 

2차원 배열을 column마다 쪼개서 누적합을 배열에 저장했다.

누적합 배열의 원소 y2에서  (y1-1) 원소를 빼줘 사이의 구간 합을 구했고 이를 x1~x2까지 반복해서 풀었다.