BOJ 15724, 주지수(Large)
ProblemSolving ·이 문제는 누적합 문제입니다.
풀이
누적합을 사용하시면 편하게 계산하실 수 있습니다.
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1] 이 식을 이용해서 누적합의 배열 dp를 만듭니다.
우리는 (x1,y1) ~ (x2,y2) 범위의 합을 구해야하는데
dp[x2][y2]에서 dp[x1-1][y2]와 dp[x2][y1-1]를 빼주면 됩니다.
하지만 중복 되는 부분이 존재합니다. dp[x1-1][y1-1] 부분이 2번 빼지기때문에 한번 더해주시면 정답을 구하실 수 있습니다
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int arr[1025][1025], dp[1025][1025];
int main() {
int n, m,t;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
scanf("%d", &arr[i][j]);
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1]; // 누적합연산식
}
cin >> t;
while (t--)
{
int a, b, c, d,ans;
scanf("%d %d %d %d", &a, &b, &c, &d); // x1,y1,x2,y2 로 생각하시면 편합니다.
ans = dp[c][d] - (dp[a - 1][d] + dp[c][b - 1] - dp[a - 1][b - 1]);
printf("%d\n", ans);
}
return 0;
}