[Silver 1] 11660번 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

 

이 문제는 DP를 통한 누적합을 구하는 문제이다.

 

DP를 통해 누적합을 구하기 위해서 아래 식을 사용한다.

누적합(X, Y) = 누적합(X-1, Y) + 누적합(X, Y-1) - 누적합(X-1, Y-1) + 요소(X, Y)

• 누적합 (X-1, Y-1)을 빼는 이유는 누적합 (X-1, Y) + (X, Y-1)에서 (X-1, Y-1)이 공통으로 들어가 한번만 합하기 위해 사용

 

누적합을 모두 구하였다면 부분합을 구해야한다.

부분합을  구하기 위해 아래 식을 사용한다.

부분합 = 누적합(X2, Y2) - 누적합(x2,y1 - 1) - 누적합(x1 - 1,y2) + 누적합(x1 - 1,y1 - 1)

• X2와 Y2까지의 부분합을 구하기 위해서는 X2, Y2까지의 누적합을 이용한다.
• 이때 필요하지 않는 구간을 빼야한다. 
• 즉, (X2, Y1-1)과 (X1 - 1, Y2)구간까지의 누적 합을 빼주고, 겹치는 구간인 (X1 - 1, Y1 - 1)을 합한다. (2번 빼줬기 때문)

 

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1025; // 최대 배열 크기
int N, M;
int arr[MAXN][MAXN] = {0, };
int dp[MAXN][MAXN] = {0, };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++)
            cin >> arr[i][j];
    }

    // 누적 합 계산
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
        }
    }

    for (int i = 0; i < M; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        // 부분 합 계산
        int result = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
        cout << result << '\n';
    }

    return 0;
}