[BOJ] 11660. 구간 합 구하기5 - JAVA 자바 ✨누적합✨

11660번: 구간 합 구하기 5

• 누적합

2차원 배열에 대해 누적합을 저장하는 경우 O(N*N)의 시간 복잡도가 주어지지만, 합을 구하는 연산이 O(1)로 줄어든다. prefixSum[a][b] 를 (1,1)부터 (a,b) 까지의 합이라고 하자

 

왼쪽이 주어진 배열이고 오른쪽이 누적합을 저장한 이차원 배열이다.

 

(1,1)에서 (2,3)까지의 누적합을 구하고자 하면 왼쪽 누적합과 위쪽 누적합을 더한 값에 교집합으로 두 번 더해지는 구간을 한 번 빼준 후 (2,3)의 배열값을 더해주면 쉽게 구할 수 있다.

 

prefixSum[2][3] = arr[2][3] + prefixSum[2][2] + prefixSum[1][3] - prefixSum[1][2]

 

따라서 다음과 같은 식을 세울 수 있다.

prefixSum[i][j] = arr[i][j] + prefixSum[i][j-1] + prefixSum[i-1][j] - prefixSum[i-1][j-1]

 

주의할 점은 누적합 배열 prefixSum[N][N]은 DP Bottom-Up 방식으로 인덱스가 1칸씩 큰 값으로 선언해주야 한다.

 

👩🏻‍💻 소스코드

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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] prefixSum = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j <= n; j++) {
                prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]
                        + Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; 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 res = prefixSum[x2][y2] - prefixSum[x1 - 1][y2] - prefixSum[x2][y1 - 1] + prefixSum[x1 - 1][y1 - 1];
            sb.append(res).append('\n');
        }
        System.out.println(sb);
    }
}