[백준] 11660번 : 구간 합 구하기 5

---

🔗 문제 링크

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

11660번: 구간 합 구하기 5

👩‍💻 코드

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    int 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] = A[i][j] + D[i][j-1] + D[i-1][j] - D[i-1][j-1];
        }
    }

    for (int i=0; i<M; i++){
        int x1;
        int y1;
        int x2;
        int y2;
    
        cin >> x1 >> y1 >> x2 >> y2;
        int answer = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
        cout << answer << "\n";
    }
}

✏️ 풀이

저번 문제에 이어서 구간합을 이용해야 하는 문제였다.

2차원 배열로 확장시켜 생각하려니 어지러웠다...

책에 나와있는대로 배열을 손으로 그려보니 이해가 됐다!

구간합을 구하고자 하는 좌표가 [2,2]라면 자기 자신의 좌표 값 A[2][2]와 이전 열과 행의 구간 합 D[2][1], D[1][2]을 모두 더한 후 중복된 값 D[1][1]을 빼주면 된다.

이 알고리즘을 바탕으로 코드의 첫 번째 for문에서 구간합 2차원 배열을 구했다.

구간합 2차원 배열에서 동일한 알고리즘을 적용하여 문제에서 요구하는 답을 구할 수 있었다.