카테고리 없음

[백준] 11660-구간 합 구하기 5(C++)

잉읭응 2020. 3. 29. 16:31
반응형

문제링크:https://www.acmicpc.net/problem/11660

 

11660번: 구간 합 구하기 5

첫째 줄에 표의 크기 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)

www.acmicpc.net

 

dp적인 생각이 있어야 하는 문제였습니다.

 (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 의 범위이므로 시간복잡도가 O(n*m)이 되면 오답입니다. ( 1억번이상 반복하기 때문에) 

즉, O(m)인 방법을 생각해야합니다.

 

 

 

해당 그림을 보면이해하기 쉽습니다. 초록색을 구하기 위해   전체 (초록 + 보라 + 파란 + 빨강) - 보라 - 파란 - 빨강입니다. 저는 각각의 좌표에 이전부터 해당좌표까지의 값을 더해 놓았습니다.

dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y11 - 1] + dp[x1 - 1][y11 - 1] 식으로 풀 수 있었습니다.

 

정답코드입니다. 

#include <iostream>
using namespace std; 
int n = 0, m = 0;
int dp[1025][1025] = { 0 };
int num = 0, x1 = 0, y11 = 0, x2 = 0, y2 = 0;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			cin >> num;
			dp[i][j] = num + dp[i][j - 1] ; // 이전행들을 중복해서 더해놓는것 1111 -> 1 2 3 4 이렇게 쌓이겠지
		}
		
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			dp[i][j] += dp[i - 1][j];
	
	while (m--) {
	
		cin >> x1 >> y11 >> x2 >> y2;
		

		cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y11 - 1] + dp[x1 - 1][y11 - 1] << '\n';
	}
}
반응형