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';
}
감사합니다