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

🌽 문제

🥕 입출력

🥔 풀이

2차원 배열의 구간합이라 사알짝 복잡하게 느껴졌다.
옛날에 무슨 집합 배울 때 외웠던 공식과 비슷한 원리로 풀 수 있다.
A합B합C = A+B+C - A교B - A교C - B교C + A교B교C 이건듯

v[i][j] = arr[0][0] 부터 arr[i][j] 까지의 누적 합으로 두고
그림판에 요래 조래 그려가며 위에서 얘기한 집합 공식의 원리를 함께 잘 열심히 고민하다보면 구간합에 대한 식을 정리할 수 있다.
설명을 적기가 귀찮거나 뭐 그런 건 아니다

🥬 코드

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

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

	int n, m;
	cin >> n >> m;
	vector<vector<int>> arr(n + 1, vector<int>(n + 1));

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

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

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

	for (int i = 0; i < m; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int ans = v[x2][y2] - v[x1 - 1][y2] - v[x2][y1 - 1] + v[x1 - 1][y1 - 1];
		cout << ans << "\n";
	}

	return 0;
}

🥜 채점