[BOJ 15724 // C++] 주지수

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

 

이번에 볼 문제는 백준 15724번 문제인 주지수이다.
문제는 아래 링크를 확인하자.

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

15724번: 주지수

배열의 사각형 영역의 합을 구하는 여러 쿼리를 처리하는 문제이다.

 

1행 1열의 칸을 좌상단 칸으로 갖고 $r$행 $c$열을 우하단 칸으로 갖는 영역의 인구를 $psum[r][c]$와 같이 나타내자.

 

이 값들을 모두 알고 있을 때, $r_1$행 $c_1$열을 좌상단 칸으로 갖고 $r_2$행 $c_2$열을 우하단 칸으로 갖는 영역의 인구는 $psum[r_2][c_2]-psum[r_1-1][c_2]-psum[r_2][c_1-1]+psum[r_1-1][c_1-1]$와 같이 나타낼 수 있다. 그림으로 그려 확인하면 더욱 이해가 쉬울 것이다.

 

$psum$의 각 값들 또한 위와 같은 원리로 미리 구해둘 수 있다. 이 값들을 미리 계산해두고 문제를 해결하자. (잘 모르겠다면 아래의 코드를 참고하자.)

 

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

#include <iostream>
using namespace std;

int R, C, K;
int psum[1025][1025];

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

	cin >> R >> C;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			cin >> psum[r][c];
			psum[r][c] += psum[r - 1][c] + psum[r][c - 1] - psum[r - 1][c - 1];
		}
	}

	cin >> K;
	while (K--) {
		int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
		cout << psum[r2][c2] - psum[r2][c1 - 1] - psum[r1 - 1][c2] + psum[r1 - 1][c1 - 1] << '\n';
	}
}