Algorithm/DP
[백준] 구간 합 구하기 5 (C++)
루시킴
2021. 10. 8. 22:21
https://www.acmicpc.net/problem/11660
11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
#include <iostream>
using namespace std;
int N, M;
int map[1025][1025];
int dp[1025][1025];
int main() {
ios_base::sync_with_stdio(false); cout.tie(NULL);cin.tie(NULL);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> map[i][j];
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]+map[i][j];
}
}
int a, b, c, d;
while (M--) {
cin >> a >> b >> c >> d;
cout << dp[c][d] - dp[c][b-1] - dp[a-1][d] + dp[a - 1][b - 1] <<'\n';
}
}
참고