백준 2167 2차원 배열의 합

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 배열이 있을 때 배열의 i,j 에서 x,y까지의 모든 요소의 합을 구하는 문제입니다.  i,j 에서 x,y 까지의 의미는 이 두영역이 만드는 사각형을 의미합니다.     

 

따라서 이 사각형의 요소의 합을 구하기 위해서는 1,1지점에서 x,y까지의 사각형의 합들을 미리 저장해 놓고 i,j에서 x,y까지의 사각형을 구하기 위해 나머지 부분을 빼주면 됩니다.

 

위 그림을 보시면 저사각형 부분에 해당하는 부분은 3,3에서 5,5까지의 부분이 됩니다. 그렇다면 저부분을 구하기 위해서

5,5까지의 사각형 영역에서 1,1에서 5,2 까지의 부분과 1,1에서 2,5까지의 부분을 각각 빼주고 2번 빼준 부분인 1,1에서 2,2까지의 영역을 더해주면 됩니다.

 

dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1] 즉 이러한 식이 나오게 됩니다.  

 (전체)  (세로 사각형) (가로)      (2번 빼진 부분)

 

또한 1,1에서 x,y까지의 사각형 넓이를 구할 때도 저는  dp[i][j-1] + dp[i-1][j] + arr[i][j] - dp[i-1][j-1] 라는 식을 통해 x,y에 해당하는 부분을 제외하고 가로 세로 사각형들을 더하고 중복된 부분을 빼주는 방법으로 구하였습니다.

 

다음은 코드입니다.

 

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N,M;
	int arr[301][301] = {0, };
	int dp[301][301] = {0, };
	cin >> N >> M;
	
	for(int i = 1; i <= N; i++)
		for(int j = 1; j <= M; j++)
			cin >> arr[i][j];
	
	
	for(int i = 1; i <= N; i++)
		for(int j = 1; j <= M; j++) {
			dp[i][j] += dp[i][j-1] + dp[i-1][j] + arr[i][j] - dp[i-1][j-1];
		}
		
	int K; cin >> K;
	while(K--) {
		int i,j,x,y;
		cin >> i >> j >> x >> y;
		cout<<dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1]<< '\n';
	}	
}