[Jungol] 정올 3136 const 구간의 합 구하기(2D)

출처: 정올(Jungol)

 Input 

5

1 2 3 4 5

6 7 8 9 0

-1 2 1 1 1

5 2 3 1 4

1 0 1 0 1

3

2 1 2 1

3 3 5 5

1 1 5 5

 

 Output 

6

13

67

 

쿼리에서 묻는 (sri, sci) ~ (eri, eci)는 다음과 같습니다.

ex) (3, 3) ~ (5, 5)

▶ 1 + 1 + 1 + 3 + 1 + 4 + 1+ 1 + 1 = 13

 

★ DP[i][j] = (0, 0) ~ (i, j) 영역 합

각 영역을 구할 때, 이중 for문으로 구하면 TLE 발생

▶ DP[i][j] = DP[i - 1][j] + DP[i][j - 1] - DP[i - 1][j - 1] + x;

    (x = 해당 위치의 숫자를 의미합니다.)

 

ex) DP[3][3] = 29 구한다고 가정 (겹쳐서 더해지는 영역을 한번 빼줍니다.)

※ DP[i][j]를 구할 때, 『-1』 로 접근하지 않기 위해 배열의 시작 인덱스 = 1로 합니다.

 

DP[i][j] = (0, 0) ~ (i, j)까지를 의미하기 때문에 

문제에서 요구하는 (sr, sc) ~ (er, ec) 영역의 합은 다음과 같이 구합니다. (겹쳐서 빼지는 영역을 한번 더해줍니다.)

▶ DP[er][ec] - DP[sr - 1][ec] - DP[er][sc - 1] + DP[sr - 1][sc - 1]

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define LM 1005
int n, m, sr, sc, er, ec;
long long DP[LM][LM];
 
int main() {
    // freopen("input.txt", "r", stdin);
    int i, j, x;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= n; ++j) {
            scanf("%d", &x);
            DP[i][j] = DP[i - 1][j] + DP[i][j - 1] - DP[i - 1][j - 1] + x;
        }
    }
 
    scanf("%d", &m);
    for (i = 1; i <= m; i++) {
        scanf("%d %d %d %d", &sr, &sc, &er, &ec);
        printf("%lld\n", DP[er][ec] - DP[sr - 1][ec] - DP[er][sc - 1] + DP[sr - 1][sc - 1]);
    }
}