https://www.acmicpc.net/problem/2167
- (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하라 -> DP
누적합을 구하는 방법을 다음의 그림과 같이 표현할 수 있습니다.
DP[x][y] - DP[x][j - 1] - DP[i - 1][y] + DP[i - 1][j - 1]
#include<iostream>
using namespace std;
int n, m, k;
int dp[301][301]{ 0 };
void input() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> dp[i][j];
dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
}
}
cin >> k;
}
void solution() {
input();
int a, b, c, d;
for (int i = 0; i < k; ++i) {
cin >> a >> b >> c >> d;
int answer = dp[c][d] - dp[c][b - 1] - dp[a - 1][d] + dp[a - 1][b - 1];
cout << answer << '\n';
}
}
int main() {
cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
solution();
return 0;
}