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

코드

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

int n, m, a[1030][1030], psum[1030][1030],x,y,x2,y2;

void FASTIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
int main() {
	FASTIO();
	cin >> n >> m;

	for(int i = 1; i < n + 1; i++) {
		for(int j = 1; j < n + 1; j++) {
			cin >> a[i][j];
            // 구간합 만들어주기, 1부터 시작해서 인덱스 에러 X
			psum[i][j] = psum[i][j - 1] + a[i][j];
		}
	}

	for(int i = 0; i < m; i++) {
		cin >> x >> y >> x2 >> y2;
		int tmp = 0;
        // 2차원 배열이라 for문 돌면서 더해줌
		for(int j = x; j <= x2 ; j++) {
			tmp += psum[j][y2] - psum[j][y - 1];
		}
		cout << tmp << '\n';
	}
	return 0;
}

풀이

2차원 배열에서의 구간 합을 구하는 문제이다. 1차원 배열에서 구간 합 만드는 것을 반복해서 각 행마다 구간 합을 구해놓는다. 이를테면, 찾는 값이 들어올 때, psum[j][y2] - psum[j][y - 1]을 해주면, j행에서 y ~ y2까지의 구간 합을 구할 수 있다. 이를 각 행마다 반복하면 2차원 배열에서 구간 합을 구할 수 있다.