[Baekjoon] 11660번: 구간 합 구하기 5

 

 

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

11660번: 구간 합 구하기 5

 

---

 

문제 해결 과정

착안

이차원 배열 내에서 $x_1$행 $y_1$열을 좌상단, $x_2$행 $y_2$열을 우하단($x_2 \geq x_1, \space y_2 \geq y_1$)으로 하는 사각형 내의 숫자들의 누적 합을 계산하기 위해, 주어진 이차원 배열과 크기가 같은 배열을 선언하여 동적계획법(dynamic programming)에 활용한다. 이때, 메모이제이션을 위한 행렬 $DP$의 $i$행 $j$열의 요소($=DP[i][j]$)에 1행 1열을 좌상단, $i$행 $j$열을 우하단으로 하는 사각형 내의 숫자들의 총합으로 저장한다.

 

위와 같이 미리 계산된 값을 사용하면, $x_1$행 $y_1$열을 좌상단, $x_2$행 $y_2$열을 우하단으로 하는 사각형 모양 내에 있는 숫자들의 누적 합 $S(x_1, y_1, x_2, y_2)$는 다음과 같이 계산할 수 있다.

 

$$S(x_1, y_1, x_2, y_2) = S(1, 1, x_2, y_2) - S(1, 1, x_1 - 1, y_2) - S(1, 1, x_2, y_1 - 1) + S(1, 1, x_1 - 1, y_1 - 1)$$

$$= DP[x_2][y_2] - DP[x_1 - 1][y_2] - DP[x_2][y_1 - 1] + DP[x_1 - 1][y_1 - 1]$$

 

구현

배열 $DP[i][j]$에 1행 1열을 좌상단, $i$행 $j$열을 우하단으로 하는 사각형 내의 숫자들을 누적한 값을 저장하는 부분에 유의하여 프로그래밍 하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int DP[1025][1025];

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

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

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

	while (M--)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << DP[x2][y2] - DP[x1 - 1][y2] - DP[x2][y1 - 1] + DP[x1 - 1][y1 - 1] << "\n";
	}

	return 0;
}

 

실행 결과