[BOJ_C++] 11660번 : 구간 합 구하기 5

• (2, 2)부터 (3, 4)까지 합을 구하라는 것은

	(2, 2)
			(3, 4)

• 위 표와 같이 구간의 합을 구하라는 것이다.

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>
#include <string>

using namespace std;
int dp[1025][1025];

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

    memset(dp, 0, sizeof(dp));
    int n, m, temp; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> temp;
            dp[i][j] = dp[i][j - 1] + temp;
        }
    }

    int x1, x2, y1, y2, sum;
    for (int i = 0; i < m; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        sum = 0;
        for (int j = x1; j <= x2; j++) {
            sum += dp[j][y2] - dp[j][y1 - 1];
        }
        cout << sum << "\n";
    }

    return 0;
}

• 최대 크기로 dp를 선언하고 모두 0으로 초기화 해주었다.
• 입력을 받으며 이전 값과 입력받은 값의 합을 계산하여 해당 행의 합을 미리 계산했다.
• x1부터 x2 행까지 y2열의 값에서 y1-1열의 값을 빼고 그 값들을 더해주면 구간의 합을 구할 수 있다.
• 구간의 합을 출력하고 프로그램을 종료해 주었다.

결과