[기본] 구간합 응용

 

들어가며

구간합의 중요성을 더 알아보고자 구간합과 관련된 응용문제를 더 풀어보고자 합니다. 지난 구간합보다는 조금 더 어려운 문제를 풀어보려고 합니다. 다시 한 번 구간합을 구해놓는 것이 얼마나 시간복잡도를 낮춰주는 지 체크해보는 시간이 될 것 같습니다.

 

 

문제

백준 11660: 구간합 구하기 5(링크)

 

 

풀이1

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int size, count;
    cin >> size >> count;

    vector<vector<int>> sumMetrix(size + 1);
    for (int i = 1; i <= size; i++)
    {
        vector<int> numList(size + 1);
        for (int j = 1; j <= size; j++)
        {
            int num;
            cin >> num;
            numList[j] = numList[j-1] + num;
        }

        sumMetrix[i] = numList;
    }

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

        int sum = 0;
        for (int j = x1; j <= x2; j++)
            sum += (sumMetrix[j][y2] - sumMetrix[j][y1-1]);

        printf("%d\n", sum);
    }
}

1차원 형태의 가로(행) 구간의 합을 모두 먼저 구합니다. 그리고 세로 영역 구간의 차이만큼 순회하면서 가로 영역(1차원)의 구간합을 더하는 형태로 작성했습니다. 정답은 맞았으나 시간이 248ms 정도 나왔습니다. 시간을 더 줄일 수 있을 것 같아서 풀이2(더 효율적인 방법)으로 한번 더 풀어봤습니다. 

 

 

풀이2

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int size, count;
    cin >> size >> count;

    vector<vector<int>> A(size + 1);
    for (int i = 1; i <= size; i++)
    {
        vector<int> numList(size + 1);
        for (int j = 1; j <= size; j++)
            cin >> numList[j];

        A[i] = numList;
    }

    vector<vector<int>> D(size + 1, vector<int>(size + 1));
    for (int i = 1; i <= size; i++)
    {
        for (int j = 1; j <= size; j++)
            D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j];
    }

    for (int i = 0; i < count; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        printf("%d\n", D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]);
    }
}

이 풀이에서는 원본 배열을 그대로 입력받아 저장하고, 2차원의 구간합을 구합니다. 구간합 배열 D의 i, j 값을 구하는 공식은 D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]; 입니다. 나름의 공식같지만, 생각해보면 바로 위, 왼쪽, 해당 값(A[i][j]) 을 모두 더하고 중복으로 더해진 위+왼쪽 값을 빼주는 방식입니다. 그리고 (x1, y1), (x2, y2) 영역의 합을 구하는 방법은 D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]입니다. 이것도 마찬가지로 1,1에서 해당 구간을 제외한 위쪽, 왼쪽을 제외(빼기)하고 중복으로 빼준 위+왼쪽 값을 더해주는 방식입니다.

이렇게 풀면 120ms로 시간이 절반으로 줄었습니다. 아무래도 풀이1의 가로영역 구간합을 구하는 반복문이 한번 더 있기 때문에 그만큼 더 오래걸리는 것으로 생각됩니다. 풀이2의 방법이 더욱 정석이며 효율적인 방법이라 추천합니다.