누적 합 2167

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

package code_test;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 배열의 크기 입력
        int N = sc.nextInt();
        int M = sc.nextInt();

        // 배열 입력
        int[][] array = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                array[i][j] = sc.nextInt();
            }
        }

        // 누적 합 배열 계산
        int[][] prefixSum = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                prefixSum[i][j] = array[i][j]
                        + prefixSum[i - 1][j]
                        + prefixSum[i][j - 1]
                        - prefixSum[i - 1][j - 1];
            }
        }

        // 쿼리 개수 입력
        int K = sc.nextInt();

        // 쿼리 처리
        for (int q = 0; q < K; q++) {
            int i = sc.nextInt();
            int j = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();

            int result = prefixSum[x][y]
                    - prefixSum[i - 1][y]
                    - prefixSum[x][j - 1]
                    + prefixSum[i - 1][j - 1];

            System.out.println(result);
        }

        sc.close();
    }
}

 

누적 합 코드 분석

int[][] prefixSum = new int[N + 1][M + 1];
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
        prefixSum[i][j] = array[i][j]
                + prefixSum[i - 1][j]
                + prefixSum[i][j - 1]
                - prefixSum[i - 1][j - 1];
    }
}

 

1. 배열 선언 및 초기화

int[][] prefixSum = new int[N + 1][M + 1];

 

• prefixSum 배열을 N + 1 x M + 1 크기로 선언.
• 이 배열은 각 위치 (i, j)까지의 부분 배열의 합을 저장.
• +1을 하는 이유는 1-based 인덱스를 사용하기 위해서. 이렇게 하면 인덱스가 0이 되는 부분을 피할 수 있음.

 

 

2. 이중 루프

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {

 

 

• i와 j는 각각 배열의 행과 열을 나타냄.
• 인덱스가 1부터 시작하는 이유는 누적 합 배열을 1-based 인덱스로 처리하기 위해서.

 

3. 누적 합 계산

prefixSum[i][j] = array[i][j]
        + prefixSum[i - 1][j]
        + prefixSum[i][j - 1]
        - prefixSum[i - 1][j - 1];

 

• prefixSum[i][j]는 (1, 1)부터 (i, j)까지의 모든 원소의 합을 저장.

구성 요소:

• array[ i ][ j ] : 현재 위치 ( i ,  j )의 원소입니다.
• prefixSum[ i - 1 ][ j ] : ( i - 1, j ) 위치까지의 부분 배열의 합입니다. 즉, 현재 위치 위쪽까지의 합.
• prefixSum[ i ] [ j  - 1 ] : ( i ,  j - 1 ) 위치까지의 부분 배열의 합입니다. 즉, 현재 위치 왼쪽까지의 합.
• prefixSum[ i - 1 ][ j - 1] : ( i - 1 ,   j - 1 ) 위치까지의 부분 배열의 합. 위쪽 왼쪽 대각선까지의 합. 이 부분은 두 번 더해질 수 있으므로 한 번 빼줌.

누적 합 배열의 예

입력 배열

1   2   4
8  16  32

 

계산 과정

1. prefixSum[ 1 ][ 1 ]:
   • prefixSum[ 1 ][ 1 ] = array[ 1 ][ 1 ]
   • prefixSum[ 1 ][ 1 ] = 1
2. prefixSum[ 1 ][ 2 ]:
   • prefixSum[ 1 ][ 2 ] = array[ 1 ][ 2 ] + prefixSum[ 1 ][ 1 ]
   • prefixSum[ 1 ][ 2 ] = 2 + 1 = 3
3. prefixSum[ 1 ][ 3 ]:
   • prefixSum[ 1 ][ 3 ] = array[ 1 ][ 3 ] + prefixSum[ 1 ][ 2 ]
   • prefixSum[ 1 ][ 3 ] = 4 + 3 = 7
4. prefixSum[ 2 ][ 1 ]:
   • prefixSum[ 2 ][ 1 ] = array[ 2 ][ 1 ] + prefixSum[ 1 ][ 1 ]
   • prefixSum[ 2 ][ 1 ] = 8 + 1 = 9
5. prefixSum[ 2 ][ 2 ]:
   • prefixSum[ 2 ][ 2 ] = array[ 2 ][ 2 ] + prefixSum[ 1 ][ 2 ] + prefixSum[ 2 ][ 1 ] - prefixSum[ 1 ][ 1 ]
   • prefixSum[ 2 ][ 2 ] = 16 + 3 + 9 - 1 = 27
6. prefixSum[ 2 ][ 3 ]:
   • prefixSum[ 2 ][ 3 ] = array[ 2 ][ 3 ] + prefixSum[ 1 ][ 3 ] + prefixSum[ 2 ][ 2 ] - prefixSum[ 1 ][ 2 ]
   • prefixSum[ 2 ][ 3 ] = 32 + 7 + 27 - 3 = 63

prefixSum[ 1 ][ 1 ] :

계산식 : prefixSum[ 1 ][ 1 ] = array[ 1 ][ 1 ] + prefixSum[ 0 ][ 1 ] + prefixSum[ 1 ][ 0 ] − prefixSum[ 0 ][ 0 ]

계산 : prefixSum[ 1 ][ 1 ] = 1 + 0 + 0 − 0 = 1

결과: prefixSum[ 1 ][ 1 ] = 1

---

prefixSum[ 1 ][ 2 ] :

계산식 : prefixSum[ 1 ][ 2 ] = array[ 1 ][ 2 ] + prefixSum[ 0 ][ 2 ] + prefixSum[ 1 ][ 1 ] − prefixSum[ 0 ][ 1 ]

 

계산 : prefixSum[ 1 ][ 2 ] = 2 + 0 + 1 − 0 = 3

결과: prefixSum[ 1 ][ 2 ] = 3

---

prefixSum[ 1 ][ 3 ] :

계산식 : prefixSum[ 1 ][ 3 ] = array[ 1 ][ 3 ] + prefixSum[ 0 ][ 3 ] + prefixSum[ 1 ][ 2 ] − prefixSum[ 0 ][ 2 ]

 

계산 : prefixSum[ 1 ][ 3 ] = 4 + 0 + 3 − 0 = 7

 

결과: prefixSum[ 1 ][ 3 ] = 7

---

prefixSum[ 2 ][ 1 ] :

계산식 : prefixSum[ 2 ][ 1 ] = array[ 2 ][ 1 ] + prefixSum[ 1 ][ 1 ] + prefixSum[ 2 ][ 0 ] − prefixSum[ 1 ][ 0 ]

 

계산 : prefixSum[ 2 ][ 1 ] = 8 + 1 + 0 − 0 = 9

 

결과: prefixSum[ 2 ][ 1 ] = 9

---

prefixSum[ 2 ][ 2 ] :

계산식 : prefixSum[ 2 ][ 2 ] = array[ 2 ][ 2 ] + prefixSum[ 1 ][ 2 ] + prefixSum[ 2 ][ 1 ] − prefixSum[ 1 ][ 1 ]

 

계산 : prefixSum[ 2 ][ 2 ] = 1 6 + 3 + 9 − 1 = 27

 

결과: prefixSum[ 2 ][ 2 ] = 27

---

prefixSum[ 2 ][ 3 ] :

계산식 : prefixSum[ 2 ][ 3 ] = array[ 2 ][ 3 ] + prefixSum[ 1 ][ 3 ] + prefixSum[ 2 ][ 2 ] − prefixSum[ 1 ][ 2 ]

 

계산 : prefixSum[ 2 ][ 3 ] = 3 2 + 7 + 2 7 − 3 = 63

결과: prefixSum[ 2 ][ 3 ] = 63

최종 누적 합 배열

0   0   0   0
0   1   3   7
0   9  27  63