취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2167번 문제인 2차원 배열의 합이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problems/2167

이 문제는 배열의 합을 구하라는 쿼리를 입력받을 때마다 직접 더해도 제한시간 내로 풀리지만, 2차원 prefix sum을 이용해 풀어보았다.

2차원의 prefix sum을 구하는 점화식은 아래의 코드와 같다.

prefix sum 구하는 점화식: psum[i][j] = arr[i][j] + psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1]

쿼리 i j x y에 대응되는 값을 계산하는 식: psum[x][y] - psum[i - 1][y] - psum[x][j - 1] + psum[i - 1][j - 1]

아래는 제출한 소스코드이다.

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

int arr[301][301];
int psum[301][301];

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

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

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

	int K; cin >> K;
	string ans = "";
	while (K--) {
		int i, j, x, y; cin >> i >> j >> x >> y;
		ans += to_string(psum[x][y] - psum[i - 1][y] - psum[x][j - 1] + psum[i - 1][j - 1]) + "\n";
	}

	cout << ans;
}