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

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

 

2차원 배열에서 구간합을 구해야한다. 이를 위해 누적합을 계산해줘야한다. 이때 문제의 규칙에 맞게

sum[i][j]=arr[i][j]+sum[i−1][j]+sum[i][j−1]−sum[i−1][j−1]

이렇게 더해주면 되는데 이때 

 

• arr[i][j]
  현재 위치 (i, j)의 값이다. 즉, 현재 칸의 값을 더해야 한다.
• sum[i-1][j]
  (1, 1)부터 (i-1, j)까지의 합이다. 즉, 현재 칸 위쪽에 있는 값들의 합을 포함한다.
• sum[i][j-1]
  (1, 1)부터 (i, j-1)까지의 합이다. 즉, 현재 칸 왼쪽에 있는 값들의 합을 포함한다.
• - sum[i-1][j-1]
  위쪽(sum[i-1][j])과 왼쪽(sum[i][j-1])에서 중복으로 더해진 영역을 빼준다. 중복된 부분은 (1, 1)부터 (i-1, j-1)까지의 합이다.

이렇게 누적합을 계산해주고 쿼리에 맞게 계산된 누적합을 출력해주면 된다.

 

 

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>>v(n + 1, vector<int>(n + 1, 0));
	vector<vector<int>>sum(n + 1, vector<int>(n + 1, 0));

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> v[i][j];
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			sum[i][j] = v[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}

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

		int result = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
		cout << result << '\n';
	}

	return 0;
}