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';
}
}
참고
'Algorithm > DP' 카테고리의 다른 글
| [백준] 13398번 : 연속합 2 (0) | 2021.11.22 |
|---|---|
| [프로그래머스] N으로 표현 (JAVA) (0) | 2021.10.16 |
| [백준] 1753번 : 최단경로 (C++, 다익스트라) (0) | 2021.09.17 |
| [프로그래머스] 정수 삼각형 (C++) (0) | 2021.09.16 |
| [백준] 10164번 : 격자상의 경로 (0) | 2021.09.03 |
댓글