문제#

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력#

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력#

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

아이디어#

전형적인 부분합 알고리즘을 이용한 문제입니다.

부분합 알고리즘은 요소들의 배열말고 다른 곳에 배열 일부 구간에 대한 합을 저장해두는 알고리즘으로 N개의 요소가 주어졌을 때 원래대로 배열의 합을 구하려면 $O(N)$이 필요하지만 부분합에서는 $O(1)$로 가능합니다.

이 문제에서 sum이 부분합 배열, arr이 요소 배열일때 부분합 배열의 점화식은 다음과 같습니다.

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

또 arr 배열의 i1행 j1열부터 i2행 j2열까지의 합은 다음과 같습니다.

sum[i2+1][j2+1] - sum[i1][j2+1] - sum[i2+1][j1] + sum[i1][j1]

1차 시도#

#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int N, M;
int *arrData;
int **arr;

int *sumData;
int **sum;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    arrData = new int[N * N];
    arr = new int *[N];

    sumData = new int[(N + 1) * (N + 1)];
    sum = new int *[N + 1];

    for (int i = 0; i <= N; ++i)
    {
        arr[i] = arrData + i * N;
        sum[i] = sumData + i * (N + 1);
        for (int j = 0; j <= N; ++j)
        {
            if (i != N && j != N)
                cin >> arr[i][j];
            if (i != 0 && j != 0)
                sum[i][j] = arr[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            else
                sum[i][j] = 0;
        }
    }
    sum[N] = sumData + N * (N + 1);

    for (int i = 0; i < M; ++i)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        cout << sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] << "\n";
    }
}

결과

맞았습니다!!

깃헙 링크 : link