[누적합] 백준 11660 구간 합 구하기 5 C++

 

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

11660번: 구간 합 구하기 5

dp[i][j] := i행의 1열부터 j열까지 배열 합 저장

∴ (p,q)부터 (r,s)까지의 구간 합 : (dp[i][s]-dp[i][q-1])의 합 (i=p부터 r까지)

#include<cstdio>

using namespace std;

int n, m, p, q, r, s, sum;
int a[1025][1025];
int dp[1025][1025];

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        sum = 0;
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            sum += a[i][j];
            dp[i][j] = sum; // (i,1)부터 (i,j)까지의 배열 합
        }
    }

    for (int i = 0; i < m; i++) {
        sum = 0;
        scanf("%d %d %d %d", &p, &q, &r, &s); // (p,q)부터 (r,s)까지 배열 합

        for (int j = p; j <= r; j++) {
            sum += (dp[j][s] - dp[j][q - 1]);
        }
        printf("%d\n", sum);
    }
}