2167번 : 2차원 배열의 합

부분사각형을 구하는 문제다. 이 문제의 핵심은 "사각형을 어떻게 만들 것인가"이다. 

위 사각형을 보자. 왼쪽 아래 꼭지점이 원점이라고 할 때, 1번 사각형의 넓이는 어떻게 나타낼 수 있을까?

그렇다. (전체 사각형의 넓이)에서 (2번사각형+4번사각형)을 빼고 (3번사각형 + 4번사각형)을 뺀 다음 (4번사각형)을 더해주면 된다.

왜 이런 방법을 쓸까?

그 이유는 넓이를 표현하기가 쉬워서 그렇다. 

이 그림을 보면 ((0,0)은 4번사각형의 왼쪽 아래 꼭짓점을 나타냄)
1) (전체 사각형의 넓이)는 (0,0) 에서 (x,y)까지의 넓이

2) (2번사각형 + 4번사각형)은 (0,0)에서 (i, y)까지의 넓이

3) (3번사각형 + 4번사각형)은 (0,0)에서 (x, j)까지의 넓이

4) (4번사각형)은 (0.0) 에서 (i, j)까지의 넓이

가 된다.

이를 dp로 저장할 때는 

1) (전체 사각형의 넓이)는 dp[x][y]

2) (2번사각형 + 4번사각형)은 dp[i][y]

3) (3번사각형 + 4번사각형)은 dp[x][j]

4) (4번사각형)은 dp[i][j]

이렇게 쉽게 지정할 수 있다.

dp[i][j]는 위의 방법을 응용해서 dp[i-1][j] + dp[i][j-1] -dp[i-1][j-1] + arr[i][j]로 정의할 수 있다.

그렇다면 1번 사각형은 dp[x][y] - dp[x][j - 1] - dp[i - 1][y] + dp[i - 1][j - 1] 로 정의가 가능하다.

#include <stdio.h>

int N, M, dp[301][301], arr[301][301], i, j, x, y;

int main() {

scanf("%d %d", &N, &M);

for (int p = 1; p <= N; ++p) {

for (int q = 1; q <= M; ++q) {

scanf("%d", &arr[p][q]);

}

}

dp[1][1] = arr[1][1];

for (int p = 1; p <= N; ++p) {

for (int q = 1; q <= M; ++q) {

if (p == 1 && q == 1) continue;

if (p == 1) {

dp[p][q] = dp[p][q - 1] + arr[p][q];

}

else if (q == 1) {

dp[p][q] = dp[p - 1][q] + arr[p][q];

}

else {

dp[p][q] = dp[p - 1][q] + dp[p][q - 1] - dp[p - 1][q - 1]+arr[p][q];

}

}

}

int T;

scanf("%d", &T);

while (T--) {

scanf("%d %d %d %d", &i, &j, &x, &y);

printf("%d\n", dp[x][y] - dp[x][j - 1] - dp[i - 1][y] + dp[i - 1][j - 1]);

}

}