백준 11660번 구간 합 구하기 5

문제 링크

누적값을 구하는 dp테이블부터 최적의 해를 찾기위해 생각을 했어야하는 dp문제였다.
dp테이블의 각 칸을 누적합으로 배치시킨 후, 문제에서 요구하는 범위합이 필요할때는 dp테이블을 구할때와 유사하게 그림을 그려서 생각해보면 편하다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n, m;
int dp[1025][1025];
int map[1025][1025];



int main() {

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

	cin >> n >> m;
	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= n; x++) {
			cin >> map[y][x]; 
			dp[y][x] = dp[y - 1][x] + dp[y][x - 1] - dp[y - 1][x - 1] + map[y][x]; //입력받으면서 dp테이블까지 정리 
																					//계속해서 최적의 해 누적합 구하기
		}
	}

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

		
		cin >> x1 >> y1 >> x2 >> y2;
		int abc= dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]; // 문제에서 원하는 범위의 합(그림으로 이해)
		answer.push_back(abc);
	}
	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << '\n';
	}

	return 0;
}