백준 11660번 구간 합 구하기 5

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

 

아이디어:

1. 구간 합 구하기의 2차원 배열로 확장

2. (2, 2) ~ (3, 4) 합은

이 아닌

이다.

3. 원본 배열과 합 배열을 따로 만들고, 합 배열은 (1, 1)부터 (i, j)까지의 합으로 표현

D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j]

4. 원하는 구간 합 (x1, y1) ~ (x2, y2) = answer

answer = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + A[x1 - 1][y - 1]

 

// 11660

#include <iostream>

using namespace std;
int table[1025][1025] = { {0} };
int D[1025][1025] = { {0} };

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, x1, y1, x2, y2, answer;

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> table[i][j];
			D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + table[i][j];
		}
	}
	
	for (int i = 0; i < M; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		answer = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1];
		cout << answer << "\n";
	}

	return 0;

}

 

모범답안:

1. 메모리 때문에 1024 * 1024 2차원 배열 생성이 어려워 전역 변수로 생성했으나,

vector<vector<int>>를 사용하면 동적으로 배열을 생성할 수 있어 스택 영역 메모리의 제약이 적어짐.

2. #include <vector>

2차원 벡터 생성

vector<vector<int>> A(N + 1, vector<int>(N + 1, 0));

 

// 11660

#include <iostream>
#include <vector>

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, x1, y1, x2, y2, answer;

	cin >> N >> M;

	vector<vector<int>> A(N + 1, vector<int>(N + 1, 0));
	vector<vector<int>> D(N + 1, vector<int>(N + 1, 0));

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> A[i][j];
			D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j];
		}
	}

	for (int i = 0; i < M; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		answer = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1];
		cout << answer << "\n";
	}

	return 0;

}