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

 

 

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

 

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

11660번: 구간 합 구하기 5

---

 

 

해결전략

 

Dynamic Programming (DP) 다이나믹 프로그래밍 
누적 합

 

 

 

---

 

 

코드

 

#include <iostream>
#include <vector>
using namespace std;

int n, m;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	vector<vector<int>>v(n + 1, vector<int>(n + 1));
	for (int x=1; x<=n; x++){
		for (int y = 1; y <= n; y++) {
			cin >> v[x][y];
		}
	}

	vector<vector<int>>dp(n + 1, vector<int>(n + 1));
	for(int x = 1; x <= n; x++){
		for (int y = 1; y <= n; y++) {
			dp[x][y] = dp[x-1][y] + dp[x][y-1] - dp[x-1][y-1] + v[x][y];
		}
	}

	int x1, y1, x2, y2;
	for (int i=0; i<m; i++){
		cin >> x1 >> y1 >> x2 >> y2;

		cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << "\n";
	}
	

	return 0;
}

 

 

---

 

유사문제

 

 

 

 

 

---