[C++] 2167: 2차원 배열의 합

쩡우·2023년 1월 18일
0

BOJ algorithm

목록 보기
37/65

문제

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보다 작거나 같다.

풀이

2차원 배열의 누적합 문제.

(3, 2) ~ (4, 4)의 누적 합을 구하고 싶다면(즉 그림에서 빨간 부분)
(0, 0) ~ (4, 4)의 누적 합에서
(0, 0) ~ (2, 4)[노랑 + 파랑]와 (0, 0) ~ (4, 1)[초록 + 파랑]의 누적 합을 빼고
(0, 0) ~ (2, 1)[파랑] 부분은 2번 빠졌으므로 다시 한 번 더해주면

결과적으로 색칠된 모든 부분에서 파랑, 노랑, 초록 부분이 1번씩 빠지게 되어 빨간 부분의 합만 남게 된다. 일반화한 식은 다음과 같다.

(x, y) ~ (i, j) 의 합
= sum[i][j] - sum[x - 1][j] - sum[i][y - 1] + sum[x - 1][y - 1]

코드

#include <iostream>

using namespace std;

void input_data(void);
void find_sum(void);
//void prt_map(void);

int n, m, k;
int sum_map[301][301];

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

	input_data();
	find_sum();

	return (0);
}

void input_data(void)
{
	cin >> n >> m;

	int i = 0;
	while (++i <= n)
	{
		int j = 0;
		while (++j <= m)
		{
			cin >> sum_map[i][j];
			sum_map[i][j] += sum_map[i - 1][j] + sum_map[i][j - 1] - sum_map[i - 1][j - 1];
			//prt_map();
		}
	}
}

void find_sum(void)
{
	cin >> k;

	int i = -1;
	while (++i < k)
	{
		int a, b, x, y;
		cin >> a >> b >> x >> y;
		cout << sum_map[x][y] - sum_map[x][b - 1] - sum_map[a - 1][y] + sum_map[a - 1][b - 1] << '\n';
	}

	return ;
}

void prt_map(void)
{
	int i = -1;
	while (++i <= n)
	{
		int j = -1;
		while (++j <= m)
			cout << sum_map[i][j] << ' ';
		cout << '\n';
	}
	cout << '\n' << '\n';
}

감사합니다

profile
Jeongwoo's develop story

0개의 댓글