BOJ 10660 C++

문제접근

구간합을 이용하여 풀 수 있다.
아래와 같은 방법으로 말이다.

주의해야할 점

예제 2번을 보아라

예제 입력

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

예제 출력

1
2
3
4

1 2 1 2

2번째 에서 1 2 1 2가 주워졌을때 3이아닌 2가 나온다. 인덱스를 잘생각하자

코드

#include <bits/stdc++.h> 
#define ll long long
using namespace std;

int dp[1025][1025];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> dp[i][j];
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + dp[i][j];
		}
	}
	while (m--)
	{
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		cout << dp[x2][y2] - (dp[x1 - 1][y2] + dp[x2][y1 - 1]) + dp[x1 - 1][y1 - 1] << "\n";
	}
}