백준(BOJ) PrefixSum 2차원 배열의 합(2167) - SILVER5

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

2167번: 2차원 배열의 합

문제

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

입력

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).

출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

문제 해결

음.. 실버 문제가 원래 이렇게 쉬웠던가... 해당 문제는 단순하게 주어진 p1좌표부터 p2좌표까지의 합을 반복문으로 구해주면 아주 간단하게 해결이 가능하다. 딱히 설명할 필요가 없는 문제인것 같다...

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pi;

ll prefix_sum(pi p1, pi p2, vector<vector<ll> >&arr){
    ll sum = 0;
    for(ll i=p1.first; i<=p2.first; i++){
        for(ll j=p1.second; j<=p2.second; j++){
            sum += arr[i][j];
        }
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // freopen("input.txt", "r", stdin);

    ll n = 0; ll m = 0;
    cin >> n >> m;

    vector<vector<ll> >arr(n+1, vector<ll>(m+1, 0));
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=m; j++){
            cin >> arr[i][j];
        }
    }

    ll k =0 ; cin >> k;
    
    pi p1; pi p2;
    for(ll i=0; i<k; i++){
        cin >> p1.first >> p1.second >> p2.first >> p2.second;
        cout << prefix_sum(p1, p2, arr) << "\n";
    }
    return 0;
}