행렬이라고 하는 2D 행렬이 있다고 가정하면 (row1, col1)을 사용하여 왼쪽 상단 모서리로 정의된 직사각형 내부 요소와 ( 행2, 열2).
따라서 행렬이 다음과 같은 경우 -
| 3 | 0 | 1 | 4 | 2 |
| 5 | 6 | 3 | 2 | 1 |
| 1 | 2 | 0 | 1 | 5 |
| 4 | 1 | 0 | 1 | 7 |
| 1 | 0 | 3 | 0 | 5 |
(2,1) 및 (4,3)으로 정의된 파란색의 위 사각형에는 합계 8이 포함됩니다.
따라서 sumRegion(2, 1, 4, 3), sumRegion(1, 1, 2, 2), sumRegion(1, 2, 2, 4)과 같은 쿼리를 수행하면 각각 8, 11, 12를 반환합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
dp라는 행렬을 정의합니다.
-
다음과 같이 작업을 초기화합니다.
-
n :=행 수. n이 0이면 반환,
-
m :=열 수
-
dp :=n x m 크기의 또 다른 행렬
-
범위 0에서 n까지의 i에 대해
-
0에서 m 사이의 j에 대해
-
j – 1 <0이면 dp[i, j]를 행렬[i, j]로 설정하고, 그렇지 않으면 (dp[i, j - 1] + matrix[i, j])
로 설정합니다.
-
-
-
범위 1에서 n까지의 i에 대해
-
0에서 m 사이의 j에 대해
-
dp[i, j] dp[i – 1, j] 증가
-
-
-
쿼리 메소드의 경우 row1, col1, row2, col2
를 사용합니다. -
ret :=dp[행2, 열2]
-
sub1 :=row1 – 1 <0일 때 0, 그렇지 않으면 dp[row1 – 1, col2]
-
sub2 :=col1 – 1 <0일 때 0, 그렇지 않으면 dp[row2, col1 - 1]
-
row1 – 1 <0 또는 col1 – 1 <0이면
-
추가 :=0
-
-
그렇지 않으면 추가 :=dp[row1 – 1, col1 – 1]
-
리턴 ret – sub1 – sub2 + 추가
예시(C++)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class NumMatrix {
public:
vector < vector <int>> dp;
NumMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
if(!n) return;
int m = matrix[0].size();
dp = vector < vector <int>>(n, vector <int> (m));
for(int i = 0; i < n; i++){
for(int j = 0 ;j < m; j++){
dp[i][j] = j - 1 < 0 ? matrix[i][j] : dp[i][j - 1] + matrix[i][j];
}
}
for(int i = 1; i < n; i++){
for(int j = 0; j < m; j++){
dp[i][j] += dp[i - 1][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int ret = dp[row2][col2];
int sub1 = row1 - 1 < 0 ? 0 : dp[row1 - 1][col2];
int sub2 = col1 - 1 < 0 ? 0 : dp[row2][col1 - 1];
int add = row1 - 1 < 0 || col1 - 1 < 0 ? 0 : dp[row1 - 1][col1 - 1];
return ret - sub1 - sub2 + add;
}
};
main(){
vector<vector<int>> mat = {{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
NumMatrix ob(mat);
cout << ob.sumRegion(2,1,4,3) << endl;
cout << ob.sumRegion(1,1,2,2) << endl;
cout << ob.sumRegion(1,2,2,4) << endl;
} 입력
[[3,0,1,4,2], [5,6,3,2,1], [1,2,0,1,5], [4,1,0,1,7], [1,0,3,0,5]] sumRegion(2,1,4,3) sumRegion(1,1,2,2) sumRegion(1,2,2,4)
출력
8 11 12