[BOJ/Bronze 1] 백준 2167 2차원 배열의 합(C++)

문제 링크

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

2167번: 2차원 배열의 합

 

문제

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

예제 입력 1

2 3
1 2 4
8 16 32
3
1 1 2 3
1 2 1 2
1 3 2 3

예제 출력 1

63
2
36

알고리즘 분류

• 누적 합

풀이

한 행당 누적 합을 구해주었는데 누적 합에 대한 개념이 확실하게 정리하지 못 해서, 2차원 배열에서 누적 합을 구하는 방법은 누적 합을 학습하면서 파악해야 할 것이다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 301
#define LL long long
#define INF 1e9

using namespace std;
int N, M, K;
int MAP[MAX][MAX];
int Sum[MAX][MAX];

void Input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> MAP[i][j];
		}
	}
	cin >> K;
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			Sum[i][j] = Sum[i][j - 1] + MAP[i][j];
		}
	}
}

void Find_Answer() {
	while (K--) {
		int Answer = 0;
		int I, J, X, Y;
		cin >> I >> J >> X >> Y;
		for (int i = I; i <= X; i++) {
			Answer += (Sum[i][Y] - Sum[i][J - 1]);
		}
		cout << Answer << "\n";
	};
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}