[백준/c++] 15724 주지수

 

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

15724번: 주지수

 

✨ 문제 풀이

 

(1,1)부터 (i, j)까지의 인구수 합을 저장하는 dp 배열을 memo[i][j]라고 하자

위에 그림과 같이

빨간 네모 + 초록색 네모 - 빨간 네모와 초록색 네모가 겹치는 네모 + 그 부분의 인구수

를 계산하면 (i, j)까지의 인구수 누적합이다

이를 점화식으로 세우면

(i, j)의 인구수 + (1,1)부터 (i-1, j)까지의 인구수 합 + (1, 1)부터 (i, j-1)까지의 인구수 합 - (1,1)부터 (i-1, j-1)까지의 인구수 합

이다.

 

그리고 우리가 원하는 건 (1,1)부터가 아닌 (x, y)부터 이다.

위에서 누적합을 구하기 위해 더하고 중복값을 빼주었던 것처럼 이번엔 반대로 빼주고 중복으로 빠진 값을 더해주면 된다

위 그림에서 보라색 네모의 인구수를 구한다고 해보자. 그럼

(4,4)까지의 인구수 합 - (초록색 네모 + 빨간 네모 - 빨간 네모와 초록색 네모가 겹치는 네모)

가 된다.

이를 점화식으로 세우면

(1, 1)부터 (i, j)까지의 인구수합 - ((1, 1)부터 (x-1, j)까지의 인구수 합 + (1, 1)부터 (i, y-1)까지의 인구수 합 - (1, 1)부터 (x-1, y-1)까지의 인구수 합)

이다.

 

코드로 작성하면 다음과 같다

#include <iostream>
using namespace std;

int N, M, K;
int total[1025][1025];
int memo[1025][1025];

int main(int argc, char const *argv[])
{

    ios::sync_with_stdio(0);
    cin.tie(0);

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

    for (int index = 1; index <= K; index++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        cout << memo[x2][y2] - (memo[x1 - 1][y2] + memo[x2][y1 - 1] - memo[x1 - 1][y1 - 1]) << '\n';
    }
    return 0;
}