[Algorithm] Baekjoon 11660번 : 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

int dp[1025][1025] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, m;
    int x1, y1, x2, y2;
    vector<long long> results;
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> dp[i][j];
 
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + dp[i][j];
        }
    }
 
    for (int i = 0; i < m; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2; // x가 행, y가 열.
 
        long long result = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
        results.push_back(result);
    }
 
    for (auto& temp : results)
    {
        printf("%lld\n", temp);
    }
}

여기에서의 DP는, 만약 x행 y열이 주어진다면 dp[x][y]는 1,1부터 x,y까지의 사각형의 누적합이다.

최종적으로 구해야할 전체 사각형에서의 일부분 사각형을 구하기 위해서는 1,1부터 해당좌표까지의 누적합이 필요하다.

 

DP테이블만 잘 업데이트 해주면 1,1에서 X,Y까지의 누적합구하는거나, X1,Y1에서 X2,Y2까지의 누적합구하는거나 메인로직은 똑같다. 

시작위치가 다를 뿐이다.

 

이 문제에 대해서 구글링 한다면, 아래와 같은 그림들을 보게 될텐데

 

여기서 DP테이블의 [x][y]는 사각형들의 중심에있는 점에 위치해있다고 생각하면, 행이나 열에 -1을 해주는 이유를 알 수 있다.