[백준(BOJ) / C++][Silver Ⅰ] 11660번 : 구간 합 구하기 5

문제

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

---

풀이

해당 문제는 구간 합 알고리즘을 사용하여 해결하였습니다.

 

먼저, 질의의 개수가 100,000개 이므로 이 문제는 질의마다 합의 값을 구하면 안된다. 그렇게 되면 무조건 시간초과가 나오기 때문에 다른 방법을 찾아봐야 하는데, 그것이 바로 '구간 합 배열' 이다.

 

이 문제는 2차원 구간 합 배열을 사용해야하는데, 해당 배열은 다음과 같이 정의할 수 있다.

 

D[X][Y] = 원본 배열의 (0, 0) 부터 (X, Y) 까지의 사각형 영역 안에 있는 수의 합.

 

일단, 합 배열을 만들어야 하는데,  2차원 구간 합 배열의 1행, 1열부터 구합니다.

구간 합 배열 1행, 1열은 다음과 같이 구합니다.

 

1행 : D[1][j] = D[1][j-1] + A[1][j]

1열 : D[i][1] = D[i-1][1] + A[i][1]

 

이를 통해 나머지 2차원 구간 합 배열을 알수 있습니다.

 

D[i][j]의 값을 채우는 구간 합 공식

: D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

 

이렇게 만든 구간 합 배열로 질의의 구간만큼의 합을 구하는 방법은

: D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1] 

 

이다,

 

 

---

소스코드

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    vector<vector<int>> A(N + 1, vector<int>(N + 1, 0));
    vector<vector<int>> D(N + 1, vector<int>(N + 1, 0));
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            cin >> A[i][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 < M; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        int result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
        cout << result << "\n" ;
    }
    
    return 0;
}