[백준 DP] 11660번 - 구간 합 구하기 5

11660번 - 구간 합 구하기 5

 

<문제>

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

11660번: 구간 합 구하기 5

 

<문제 풀이>

문제 접근은 쉽다. 값을 입력 받아 배열에 저장하고 시작점부터 끝점까지의 누적 합을 구하면 된다. 

시간초과될 것을 알면서도 일단은 이중 for문을 사용하여 코드를 작성하고 제출해봤다. 

 좌표값을 입력 받을 때 사용하는 이중 for문은 필요한 과정이라고 생각을 했고, 누적 합을 구하는 과정에서 사용되는 이중 for문을 없애보려 코드 수정을 해보았다. 

이 과정에서 2차원 배열을 하나 더 생성하였고 새로 생성한 2차원 배열에는 (1, 1) -> (a, b)까지의 누적 합을 저장했다. 

Ex)

arr[][]     -->   dp[][]

1   2             1     3

3   4             4     10

문제에서 좌표 값을 입력 받을 때 위와 같이 누적 합도 같이 저장했다. 

하지만 dp 배열에 저장되어 있는 값은 시작점이 무조건 (1, 1)이다. 문제는 시작점이 (1, 1)이 아닐 수도 있다는 점이다.

만약 (1, 2) -> (2, 2)를 입력 받았다고 해보자. 

문제에서 원하는 출력 값은 6이다. dp[2][2]에는 출력 값을 구하는 데 필요없는 arr[1][1], arr[2][1]의 값이 누적 되어있다. 

결과적으로 문제에서 원하는 답은 dp[2][2]에서 dp[2][1]의 값을 뺀 값이다. 

2x2 배열에서는 점화식이 잘 보이지 않지만 문제 예시에 있는 4x4 배열에서는 점화식을 찾을 수 있을 것이다. 

점화식(입력): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j]

점화식(출력): dp[x2][y2] - (dp[x1 - 1][y2] + dp[x2][y1 - 1] - dp[x1 - 1][y1 - 1])

 

<코드>

• 시간초과 코드

#include <iostream>
using namespace std;

int N, M;
int dp[1025][1025] = { 0, };

int main() {
	cin >> N >> M;

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

	int sum;
	int x1, x2, y1, y2;
	while (M-- > 0) {
		sum = 0;
		cin >> x1 >> y1 >> x2 >> y2;

		for (int i = x1; i <= x2; i++) {
			for (int j = y1; j <= y2; j++) {
				sum += dp[i][j];
			}
		}
		
		cout << sum << endl;
	}

	return 0;
}

 

• 해결 코드

#include <iostream>
using namespace std;

int N, M;
int arr[1025][1025] = { 0, };
int dp[1025][1025] = { 0, };

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

	cin >> N >> M;

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

	int sum;
	int x1, x2, y1, y2;
	while (M-- > 0) {
		sum = 0;
		cin >> x1 >> y1 >> x2 >> y2;
		
		sum = dp[x2][y2] - (dp[x1 - 1][y2] + dp[x2][y1 - 1] - dp[x1 - 1][y1 - 1]);
		cout << sum << '\n';
	}

	return 0;
}

 

<결과>

 

 

2022.12.28