2차원에서의 부분 합 -백준 11660 구간 합 구하기 5

부분합은 1차원뿐만 아니라, 2차원 배열에서도 사용이 가능합니다

2차원 배열 Arr[][]이 주어진다고 했을 떄, A[x1,y1]에서 A[x2,y2]까지의 직사각형 구간의 합을 계산한다고 가정해봅사다.

 

그 전에, 부분 합 배열은 다음과 같습니다.  이 배열을 psum이라고 표현하겠습니다.

 

부분 합 배열을 구하기 전에 숫자가 다음과 같이 있다고 가정해봅니다.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

 

psum은 2차원 배열의 부분 합입니다. 즉 [0,0] - [x,y]까지의 부분합입니다.

[0,0] -> [0,0] - [0,0]까지의 부분합 

[0,1] -> [0,0] - [0,1]까지의 부분합, [0,2] -> [0,0] - [0,2]까지의 부분합...[0,3] -> [0,0] - [0,3]까지의 부분합.

 

이를 토대로 계산하면 psum의 0번쨰 행은 1 3 6 10 이 됩니다.

 

이제 1번쨰 행의 경우이다.

[1,0] -> [0,0] - [1,0]까지의 부분합이고, (0,0) (1,0)가 범위에 들어갑니다.

[1,1] - > [0,0] - [1,1]까지의 부분합이고, (0,0), (0,1), (1,0), (1,1)가 범위에 들어갑니다.

[1,2] - > [0,0] - [1,2]까지의 부분합이고 (0,0) , (0,1), (0,2), (1,0), (1,1), (1,2)가 범위에 들어갑니다.

 

이를 토대로 계산하면 psum의 1번쨰 행은 3 8 15 24가 됩니다.

 

psum의 (1,1)은 (0,0), (0,1), (1,0), (1,1)이 들어갑니다.

psum의 (0,1)은 (0,0), (0,1) 이고 psum의 (1,0)은 (0,0), (1,0)입니다.

psum의 (0,0)은 (0,0입니다.

 

psum의 (1,1)을 계산하기 위해서는 , 일단 psum의 (0,1) 과 psum의 (1,0)을 더해줍니다.

그렇게 된다면, psum(0,1) -> (0,0) , (0,1) , psum(1,0) -> (0,0), (1,0)가 됩니다.

psum의 (1,1)은 (0,0), (0,1), (1,0), (1,1)인데 (0,0)이 2번 들어갑니다.

 

그래서 psum의 (0,0)을 빼줍니다 (0,0)

그렇게 되면  현재 총 (0,0), (0,1), (1,0)가 존재합니다. 그리고 (1,1)은 기존 배열의 숫자를 더해주면 됩니다.

 

즉 , psum[i][j] = psum[i-1][j] + psum[i][j-1]  + 원래배열[i][j] - psum[i-1][j-1]

이라는 점화식이 나옵니다.

---

2차원 부분 합을 이렇게 정해두고,  정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 합니다.

 

다음과 같은 그림은 [y1,x1]부터 [y2,x2]까지의 그림은 굵은 선으로 표시되어 있습니다.

https://velog.io/@sunjoo9912/%EC%A2%85%EB%A7%8C%EB%B6%81-17%EC%9E%A5-%EB%B6%80%EB%B6%84%ED%95%A9

 

이 구간의 합을 구하는 방법은, 부분합 배열 [y2,x2]에서 색칠된 구간을 뺴는 것입니다. 

즉 [y2,x2]에서 [y2,x1-1]을 뺴고, [y1,x2-1]을 뺴줍니다. 이떄, 진하게 색칠된 구간은 2번 뺴지므로, [y1-1,x1-1]구간을 다시 더해주면 최종적으로 

[y1,x1]에서 [y2,x2]까지의 직사각형 구간의 합을 구할 수 있습니다.

 

psum[y2, x2] - psum[y2, x1-1] - psum[y1-1, x2] + psum[y1-1, x1-1]

---

 

 전체 소스코드->

 #include <iostream>
using namespace std;
 
// 백준 구간 합 구하기 5 (2차원 배열에서의 구간 합)
/*
A[x1,y1] - A[x2,y2]까지의 구간의 합
2차원 DP배열 -> DP(x,y) -> [0,0] - [x,y]까지의 직사각형 원소의 합
*/


 int arr[1025][1025];
int dp[1025][1025];
 
int main(void){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n,m;
    cin >> n >> m;
 
    int temp = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cin >> arr[i][j];
        }
    }
 
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){    
               dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]; 

        }
    }
 
    for(int i = 0;i<m;i++){
        int x,y,x2,y2;
        cin >> x >> y >> x2 >> y2;  
        int diff = dp[x2][y2] - dp[x-1][y2] - dp[x2][y-1] + dp[x-1][y-1];
        cout << diff << '\n';
    }
}