[백준 16507] 어두운 건 무서워

 

 

문제 : https://www.acmicpc.net/problem/16507

16507번: 어두운 건 무서워

 

2차원 배열 형태로의 부분 합 문제이다.

부분 합을 구할 때와 범위 합을 리턴할 때 계산을 주의하면 된다.

또한 평균을 구하는 것이니 부분 합을 칸의 개수로 나눠주면 된다.

 

#include <iostream>
using namespace std;

int r, c, q;
int table[1001][1001];
int psum[1001][1001];

void partialSum(){
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + table[i][j];
}

int getAvg(int r1, int c1, int r2, int c2){
    int summ = psum[r2][c2] - psum[r1-1][c2] - psum[r2][c1-1] + psum[r1-1][c1-1];
    int cnt = (r2-r1+1) * (c2-c1+1);
    return summ / cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> r >> c >> q;
    
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            cin >> table[i][j];
    
    partialSum();
    
    for(int i = 0 ; i < q; i++){
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << getAvg(r1, c1, r2, c2) << '\n';
    }
    
    return 0;
}