c++ 백준_11660_"구간 합 구하기 5"

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

11660번: 구간 합 구하기 5

일단

행 방향으로 누적합을 구했다

​

그럼 그림의 예시는

​

1 3 6 10

2 5 9 14

3 7 12 18

4 9 15 22

​

가 된다.

​

(2,2) 에서 (3,4) 까지 합은

정해둔 범위(빨간색)에서

가장 오른쪽(초록색)은

해당 범위 내 모든 행렬 값의

최종 누적합이 된다.

 

그 값에서

정해둔 범위의 바로 왼쪽(주황색) 값들을

빼주면

해당 범위의 합이 나온다.

 

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

int main(void) {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, M;
	cin >> N >> M;

	vector<vector<int>> num(N + 1, vector<int>(N + 1,0));
	vector<vector<int>> arr(N + 1, vector<int>(N + 1,0));
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> num[i][j];
			arr[i][j] = num[i][j];
		}
	}

	for (int i = 1; i <= N; i++) {
		
		for (int j = 2; j <= N; j++) {
			arr[i][j] += arr[i][j - 1];
		}
	}

	int x1, y1, x2, y2;

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

		int result = 0;
		if (x1 != x2 && y1 != y2) {	
			for (int k = x1; k <= x2; k++) {
				result += arr[k][y2];
			}

			for (int k = x1; k <= x2; k++) {
				result -= arr[k][y1 - 1];
			}
		}
		else if (x1 == x2 && y1 != y2) {
			result = arr[x2][y2];
			result -= arr[x1][y1 - 1];
		}
		else if (x1 != x2 && y1 == y2) {
			for (int k = x1; k <= x2; k++) {
				result += arr[k][y2] - arr[k][y1 - 1];
			}
		}
		else if (x1 == x2 && y1 == y2) {
			result = num[x1][y1];
		}
		cout << result << "\n";

	}

}