[BOJ] 11660

구간 합 구하기 5

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

분류

• Silver 1

• 다이나믹 프로그래밍
• 누적 합

해법

mat[i][j]는 아래와 같은 영역을 모두 더한 값을 나타내게 해줍니다.

x1, y1, x2, y2가 입력으로 들어왔을 때,
mat[x2][y2]에서 아래 그림의 노란색 영역과 파란색 영역을 빼줍니다.

그러면 초록색 영역은 두 번 빼준 게 되니까 초록색 영역을 더해주면 원하는 값을 구할 수 있습니다.

정답 코드

/*
BOJ 11660: 구간 합 구하기 5
*/

#include <bits/stdc++.h>
using namespace std;

int N, M;
int mat[1050][1050];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> mat[i][j];
            mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
        }
    }
    while (M--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << mat[x2][y2] - mat[x2][y1 - 1] - mat[x1 - 1][y2] + mat[x1 - 1][y1 - 1] << "\n";
    }
    return 0;
}