[백준 C++] 11660 구간 합 구하기 5 - 다이나믹프로그래밍

11660번: 구간 합 구하기 5

#include <iostream>
using namespace std;

int DP[1025][1025];

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

	int N, M;
	cin >> N >> M;

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

	for (int i = 0; i < M; ++i)
	{
		int X1, Y1, X2, Y2;
		cin >> X1 >> Y1 >> X2 >> Y2;
		cout << DP[X2][Y2] + DP[X1 - 1][Y1 - 1] - DP[X1 - 1][Y2] - DP[X2][Y1 - 1] << '\n';
	}
}

---

 

일반적인 1차원 배열 구간합 문제에서 2차원 행렬의 구간합을 구하는 문제로 확장된 유형입니다.

 

1행 1열 ~ i행 j열 까지의 구간합을 점화식으로 나타내면 다음과 같습니다.

DP[i][j] = DP[i][j - 1] + DP[i - 1][j] - DP[i - 1][j - 1] + Num[i][j]

 

그리고 X1행 Y1열 ~ X2행 Y2열 까지의 구간합은 다음과 같은 식을 이용해서 구할 수 있습니다.

Sum = DP[X2][Y2] + DP[X1 - 1][Y1 - 1] - DP[X1 - 1][Y2] - DP[X2][Y1 - 1]