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

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

사각형의 넓이를 다루듯이 풀면 쉽게 풀 수 있다. dp를 구할 때에도 왼쪽, 위의 dp값에서 왼쪽 위 대각선의 dp값을 빼고 현재 위치에 있는 수를 더하면 dp를 구할 수 있다.

 

답을 구할 때 사각형의 넓이를 구하듯이 전체에서 부분을 빼주고 교집합을 처리하는 식으로 구해주자.

 

#include <cstdio>
int main(void){
	int N, M, x1, x2, y1, y2;
	scanf("%d %d", &N, &M);
	int array[N+1][N+1]={};
	int dp[N+1][N+1]={};
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			scanf("%d", &array[i][j]);
			dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + array[i][j]);
		}	
	}
	for(int i=0; i<M; i++){
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		printf("%d\n", dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]);
	}
}