[백준 16507번] 어두운 건 무서워(C++ / preSum, dp)

 

아이디어

presum을 미리 구해두고 (나는 dp라고 명명)

빨간색 구역의 합은 dp[r2][c2]에서 주황색 두부분을 빼고, 초록색 영역을 다시 더해줌으로써 구할 수 있다.

 

C++풀이

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int R,C,Q;
int board[1000][1000];
int dp[1001][1001];
int r1,c1,r2,c2;

int main(void)
{
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> R >> C >> Q;
    for(int i = 0 ; i< R; i++)
    {
        for(int j = 0 ; j< C ; j++)
        {
            int tmp;
            cin >> tmp;
            board[i][j] =tmp;
        }
    } 
    dp[1][1] = board[0][0];
    for(int i = 1 ; i<=R; i++)
    {
        for(int j = 1 ; j<=C ; j++)
        {
            dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+board[i-1][j-1];
        }
    }
    
    for(int i = 0 ; i< Q; i++)
    {
        cin >> r1 >> c1 >> r2 >> c2;
        cout <<(dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1]+dp[r1-1][c1-1])/((r2-r1+1)*(c2-c1+1))<<endl;
    }

}