[BOJ]백준 11660번: 구간 합 구하기5/DP

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

전형적인 DP문제인 구간합 구하기이다 !!

 

1. 문제 정의

(x1, y1)부터 (x2, y2)까지의 직사각형 영역에 있는 element들의 합을 구한다

 

2. Subproblem & Recurrence

(0,0) ~ (X2,Y2)까지의 구간합은 (X1-1,Y2)의 구간합+ (X2,Y1-1)의 구간합 - (X1-1,Y1-1)의 구간합으로 나타낼 수 있다(아래의 그림 참조)

 

3. Memoization & Recurrence relation

따라서 2차원 배열을 생성해서 (R,C)까지의 구간합을 저장한다

이 때, 2번에서 구한 recurrence relation에서 각 좌표의 dp값은 이전 좌표값에 dependent하므로, iteration을 이용해서 (0,0)부터 bottom-up방식으로 구한다.

 

4. Time Complexity

(R,C)의 값을 구하는 과정에서, 세 번의 산술 연산은 각각 O(1)이 걸리고 모든 이차원 좌표에 대해 실시하므로 총 시간복잡도는 O(n²)이다

 

5. Code

#include <cstdio>
int n, m,dp[1025][1025],arr[1025][1025];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			scanf("%d", &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;
		scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
		printf("%d\n", dp[y2][x2] - dp[y1 - 1][x2] - dp[y2][x1 - 1] + dp[y1 - 1][x1 - 1]);
	}
	return 0;
}