[Algorithm] 2D Prefix Sum BOJ 23247

본 문서는 이차원 배열에서 누적합 알고리즘을 적용하는 방법에 대해 다루고 있습니다. 

BOJ 23247 Ten 문항을 기반으로 설명합니다.

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

 

이차원 배열에서 누적합을 구하는 방법

1. 행 방향으로 원소들의 누적합을 계산한다.

    // 2차원 누적합 계산 로직
    // [Logic1] row(행) 방향으로 모든 원소의 합을 구한다.
    for (int y = 1; y <= n; y++) {
        for (int x = 1; x <= m; x++) {
            // 이전 열까지의 합(apple_sum[y][x-1])에 현재 값을 더한다.
            apple_sum[y][x] = apple_sum[y][x-1] + apple[y][x];
        }
    }

 

2. 행 방향으로 누적된 누적합 배열을 기반으로

열 방향으로 누적합을 계산한다. 

 

그러면 최종적으로 2차원 배열 누적합이 완성된다.

apple_sum 누적합의 1행2열(17)에는

기존 apple 배열의 0행0열부터 1행2열까지의 합이 담기게 된다. 

    // [Logic2] Column(열) 방향으로 모든 원소의 합을 구한다.
    for (int y = 1; y <= n; y++) {
        for (int x = 1; x <= m; x++) {
            // 이전 행까지의 합(apple_sum[y-1][x] + apple[y-1][x])에 현재 값을 더한다.
            apple_sum[y][x] = apple_sum[y-1][x] + apple_sum[y][x];
        }
    }

 

그렇다면 1행1열 원소부터 2행3열까지의 원소의 합은 어떻게 계산할까?

 

단순히 누적합의 2행3열 원소를 출력해서는 안된다.

apple_sum[2][3]의 원소 33은

기존 apple 배열의 0행0번째 원소부터 2행3번째 원소의 모든 합을 계산한 것이기 때문이다.

 

그렇기에 1행1열부터 2행3열까지의 배열의 합을 구하기 위해서는 

apple_sum[2][3] (0행0열~2행3열) 에서

apple_sum[2][0] (0행0열~2행0열), apple_sum[0][3] (0행0열~0행3열) 을 빼준뒤

마지막으로 2번 빼진 apple_sum[0][0] (0행0열) 을 더해주면 된다.

 

    int ans = 0;
    for (int y = 1; y <= n; y++) {
        for (int x = 1; x <= m; x++) {
            for (int y_idx = y; y_idx <= n; y_idx++) {
                for (int x_idx = x; x_idx <= m; x_idx++) {
                    int rect = apple_sum[y_idx][x_idx] - apple_sum[y-1][x_idx]
                                - apple_sum[y_idx][x-1] + apple_sum[y-1][x-1];

                    if (rect == 10) ans++;
                    if (rect > 10) break; // 가지치기
                }
            }
        }
    }
    
    cout << ans << endl;

 

https://github.com/novvvv/PS2025/blob/main/202509/23247.cpp