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

Link

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

풀이 과정

• 누적 합에 대한 계산으로, 2차원 DP를 이용하여 합을 누적하는 것으로 계산

1. (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하라 -> DP

누적합을 구하는 방법을 다음의 그림과 같이 표현할 수 있습니다.

DP[x][y] - DP[x][j - 1] - DP[i - 1][y] + DP[i - 1][j - 1]

• (0,0)부터 (x,y)까지를 포함하는 검은색 구간을 전부 합한 값이 (x,y)위치에 누적합으로 계산되어 있습니다.
  이 때 빨간색과 초록색 누적합을 빼면 (i,j)부터 (x,y)까지의 누적합을 구한 것처럼 보일지 모르지만, 빨간 사각형과 초록 사각형은 보라색 사각형이라는 범위를 중복으로 가지고 있습니다.
  따라서 전체에서 빨간색, 초록색 사각형을 빼고, 다시 중복된 범위인 보라색 사각형 범위를 더해주면 원하는 결과를 얻을 수 있습니다.

정답 코드

#include<iostream>
using namespace std;

int n, m, k;
int dp[301][301]{ 0 };

void input() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> dp[i][j];
			dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
		}
	}
	cin >> k;
}

void solution() {
	input();
	int a, b, c, d;
	for (int i = 0; i < k; ++i) {
		cin >> a >> b >> c >> d;
		int answer = dp[c][d] - dp[c][b - 1] - dp[a - 1][d] + dp[a - 1][b - 1];
		cout << answer << '\n';
	}
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}