[백준 / C++] 11660번 구간 합 구하기 5 - (1), DP

백준 11660번 구간 합 구하기 5 문제 

 

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

예제 입력 1 

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

예제 출력 1 

27
6
64

예제 입력 2 

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

예제 출력 2 

1
2
3
4

 

---

 

구간 합 구하기 문제 풀이

 

먼저, 이 문제의 첫번째 조건을 보면 표의 크기 N과 구해야 하는 횟수 M의 범위가 (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 이렇게 나온다. 사실 구해야 하는 횟수의 최댓값이 10만이므로 일반적인 O(N) 코드로는 나타낼 수 없다. 따라서, 시간 복잡도가 O(N)이하여야만 이문제를 풀 수 있을 것이다라고 생각했다.

 

또한, 우리가 구해야하는 것이 표의 (x1, y1)부터 (x2, y2)의 합이다. 따라서, 규칙이 확실히 존재하면서, 많은 횟수를 반복해야하니 DP를 떠올릴 수 있다.

 

문제에 주어진 예제 1번을 가지고 DP의 점화식을 세워보았다. 

(참고로 문제에서 X는 행, Y는 열이라고 주어진다)

 

(설명을 예제 2의 입력이 아니긴한데.. 어차피 상관없으니 그냥 보길 바란다..ㅋㅋ)

 

위 그림과 같이 아래 초록색 표는 다음과 같은 규칙을 적용하여 만든 표이다.

 

코드로는 이렇게 나타낸다.

현재 좌표의 원래 값 + 이전 행의 DP 값  + (같은 행 이전 열 값 - 이전 행 이전 열 값) 

int eex;
cin >> eex;
dp[i][j] = eex + dp[i - 1][j] + (dp[i][j - 1] - dp[i - 1][j - 1]);

 

만약, ( X : 2 , Y : 2)를 살펴본다고 했을 때  X : 2, Y : 2를 포함한 이전 모든 값들을 더해주는 식으로 해서 표를 만든다. 

이렇게 한 이유는 특정 범위를 구할 때 그 이전 값들을 빼주면 되기 때문이다.

 

이렇게 DP로 만든 배열 표가 완성된다면 이제 반복되서 들어오는 좌표값들에 맞춰서 출력을 해주면 된다.

 

---

 

여기서 만약  3,3 ~ 4,4 까지의 값들에 합을 구한다면 아래와 같은 점화식을 만들어주면 된다. 

s_x, s_y 는 구할려고 하는 좌표의 시작 X, Y 좌표

e_x, e_y는 구할려고 하는 좌표의 마지막 X, Y 좌표이다.

int s_x, s_y, e_x, e_y;
cin >> s_x >> s_y >> e_x >> e_y;

int result = dp[e_x][e_y] - dp[e_x][s_y - 1] - (dp[s_x - 1][e_y] - dp[s_x - 1][s_y - 1]);

 

밑에와 같이 엑셀 표로 정리하자면 DP 시작지점 3,3 : 12 , 끝지점 4,4 : 24 이다.

여기서 24 -  ( dp[e_x][s_y-1] = 12  )- ( dp[s_x - 1][e_y] = 10 ) + ( dp[s_x - 1][s_y - 1] = 5) == 7

이렇게 결론이 나는 것을 확인할 수 있다. 

 

위와 같은 진행으로 10만번을 해도 한번 계산할 때마다 시간 복잡도는 O(1)이 걸리기 때문에 금방 구할 수 있게 된다. 

---

구간 합 구하기 전체 코드 

 

#include<iostream>

using namespace std;
int num[1025][1025] = { 0 };
int dp[1025][1025] = { 0 };

int n, m;

void cacluate(pair<int, int> start, pair<int, int> end) {
	return;
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			//cin >> num[i][j];
			int eex;
			cin >> eex;
			dp[i][j] = eex + dp[i - 1][j] + (dp[i][j - 1] - dp[i - 1][j - 1]);
		}
	}


	for (int i = 0; i < m; i++) {
		int s_x, s_y, e_x, e_y;
		cin >> s_x >> s_y >> e_x >> e_y;

		int result = dp[e_x][e_y] - dp[e_x][s_y - 1] - (dp[s_x - 1][e_y] - dp[s_x - 1][s_y - 1]);

		cout << result << '\n';
	}

	return 0;
}