백준 2167번 2차원 배열의 합 // C++

문제

 

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

입력

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y).

출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 32bit-int 범위를 초과하지 않는다.

 

---

 

풀이

 

합을 구하는 경우의 수가 최대 10,000개이기 때문에 for문을 사용해서 그때 그때 합을 구하면 시간이 오래걸리게 된다.

 

따라서 DP 방식을 사용하여 배열의 합을 구해야 한다.

 

먼저, (1,1)에서 (X,Y)까지의 총합을 담고 있는 배열을 하나 선언한다.

 

sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j]

 

(X,Y)까지의 총합은 위의 그림에서 "초록 + 파랑 - 노랑 + (X,Y)의 값"으로 구할 수 있다.

 

 

이렇게 (1,1)에서부터 각 좌표까지의 총합을 구했다면, (A,B)에서 (C,D)까지의 총합 역시 구할 수 있다.

 

 

 

 

(A,B)에서 (C,D)의 합은, sum(C,D) - sum(A-1,B) - sum(A,B-1) + sum(A-1,B-1)로 구할 수 있다.

 

마지막에 sum(A-1,B-1)을 더해주는 이유는 위 그림에서 초록 부분이 뺄셈에서 두번 빠지기 때문이다.

---

 

코드

#include <iostream>

using namespace std;

int N, M;
int arr[301][301];
int sum[301][301] = { 0, };

void calc();
void solve();

int main() {
	cin >> N >> M;

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

	calc();

	solve();

	return 0;
}

void calc() {
	sum[1][1] = arr[1][1];

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

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

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

}

void solve() {
	int K;

	cin >> K;

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

		cout << sum[y2][x2] - sum[y1 - 1][x2] - sum[y2][x1 - 1] + sum[y1 - 1][x1 - 1] << "\n";
	}
}