11660 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

\( N \times N \) 개의 수가 \( N \times N \) 크기의 표에 채워져 있고 x1행 y1열부터, x2행 y2열까지의 합을 구하는 프로그램을 작성하는 문제.

 

DP 문제로, 1행 1열 부터 자기자신까지의 합을 저장하여 DP 배열을 만든다.

\( DP[x][y] = DP[x-1][y] + DP[x][y-1] - DP[x-1][y-1] + A[x][y] \)

이 점화 식을 시각적으로 표현하면 다음 그림과 같다.

target 이 DP[x][y] 일때, DP[x-1][y] 과 DP[x][y-1] 를 더하면 DP[x-1][y-1]이 2개, DP[x][1] ~ DP[x][y-1] 까지 합, DP[1][y] ~ DP[x-1][y] 까지 합이 되므로,

DP[x-1][y-1]을 빼고 해당 자리의 값을 더하면 DP[y][x] = (1, 1) 부터 (x, y) 까지의 합이 된다.

 

마찬가지의 원리로 (x1, y1) ~ (x2, y2)를 구하면 된다.

 

\(  (x1, y1) to (x2, y2) = DP[x2][y2] - DP[x1-1][y1] - DP[x1][y1-1] + DP[x1-1][y-1] \)

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin >> dp[i][j];
            dp[i][j] += dp[i][j-1];
            dp[i][j] += dp[i-1][j];
            dp[i][j] -= dp[i-1][j-1];
        }
    }
 
    int x1, y1, x2, y2;
    while(m--)
    {
        cin >> y1 >> x1 >> y2 >> x2;
        cout << dp[y2][x2]-dp[y2][x1-1]-dp[y1-1][x2]+dp[y1-1][x1-1] << endl;
    }
 
    return 0;
}