[Baekjoon/C++] 2167번 - 2차원 배열의 합

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).

 

출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

 

---

풀이

#include <iostream>
using namespace std;

int N, M, K;
int arr[301][301];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

			arr[i][j] += (arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1]);
		}
	}

	cin >> K;
	while (K--) {
		int i, j, x, y;
		cin >> i >> j >> x >> y;

		cout << arr[x][y] - arr[x][j - 1] - arr[i - 1][y] + arr[i - 1][j - 1] << '\n';
	}

	return 0;
}

 

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

			arr[i][j] += (arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1]);
		}
	}

 (1, 1)부터 (i, j)까지의 누적합을 구하는 부분의 코드이다. 바로 왼쪽 칸의 숫자와 윗칸의 숫자를 현재 칸의 숫자에 더한다. 이때 현재 칸에서 왼쪽 대각선 위의 칸을 중복으로 더하게 되므로 이를 빼도록 했다.

 

	while (K--) {
		int i, j, x, y;
		cin >> i >> j >> x >> y;

		cout << arr[x][y] - arr[x][j - 1] - arr[i - 1][y] + arr[i - 1][j - 1] << '\n';
	}

 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 부분의 코드이다. 범위에 포함되지 않는 왼쪽의 칸들과 위쪽의 칸들을 마지막 칸의 숫자에서 빼도록 했다. 이때 중복해서 2번 빼는 범위가 생기므로 이를 더하도록 했다.