백준 11660번 구간 합 구하기 5 C++

https://www.acmicpc.net/problem/11660

 

dp 테이블을 이용하여 누적 합을 저장해서 풀 수 있는 문제이다.

예제의 숫자들을 각 행마다 누적 합을 저장하여 저장한다.

(2,2)부터 (3,4) 까지의 합은

이 부분의 합을 구하면 되기 때문에

dp[2][4]-dp[2][2-1] + dp[3][4]-dp[3][2-1] = (14 - 2) + (18 - 3) = 27 이렇게 구할 수 있다.

이것을 코드로 나타내면

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_map>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, val, x1, x2, y1, y2;
	cin >> n >> m;
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> val;
			dp[i][j] = dp[i][j - 1] + val;
		}
	}
	while (m--) {
		int sum = 0;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int i = x1; i <= x2; i++) {
			sum += dp[i][y2] - dp[i][y1 - 1];
		}
		cout << sum << "\n";
	}
};

이런 식으로 코드를 짤 수 있다.