[C++] 백준11660: 구간 합 구하기 5

오늘은 2차원 배열로 확장되는 구간합 알고리즘을 풀었다.

# include <iostream>
# include <vector>
using namespace std;

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

	int N, M;
	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++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int result;
		result = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1];
		cout << result << '\n';
	}
	
}

기본적인 원리는 구간합 구하기 4와 같다.

2차원 벡터 선언시 주의 할점은

길이가 N이 아니라 N+1이라는 점이다.
그렇게 해야만 D[1][1]을 초기화 할때 인덱스 범위 초과가 안난다.

첫번째 이중 for문의 i가 1로 초기화 되는것도 이와 같은 이유이다.
D의 0번 인덱스에 접근하는 연산을 하기 때문이다.

두번째 for문에서 M번만큼 반복문을 돌려서
흔히 알려진 구간합 구하기 연산으로 답을 구하면 된다

내일 아무것도 안보고 한번 더 풀어봐야겠다.