(C++) - 백준(BOJ) 16507 : 어두운건 무서워

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

16507번: 어두운 건 무서워

2차원 누적합 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

r(행), c(열), q(질의 개수), board(입력받을 2차원 배열), sum(누적합을 저장할 2차원 배열) 을 선언합니다.적절히 입력받습니다.

 

📔 풀이과정

 1. 가로방향으로 구간합을 구해줍니다. 첫 번째 열에는 그냥 board의 값이 저장됩니다.

 2. 세로방향으로 구간합을 구해줍니다. 첫 번째 행에도 그냥 board의 값이 저장됩니다.

 

📔 정답출력

q만큼 r1, c1, r2, c2를 입력받고 구간에 대한 합을 O(1)만에 출력합니다.

---

📕 Code

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

ll r, c, q, board[1001][1001], sum[1001][1001];
int main(){
    cin >> r >> c >> q;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            cin >> board[i][j];
        } 
    }
    
    //가로 방향으로 구간합
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            sum[i][j] = sum[i][j-1] + board[i][j];
        }
    }
    //세로 방향으로 구간합
    for(int i = 1; i <= c; i++){
        for(int j = 1; j <= r; j++){
            sum[j][i] = sum[j-1][i] + sum[j][i];
        }
    }
    
    while(q--){
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << (sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1]) / ((r2 - r1 + 1) * (c2- c1 + 1)) << '\n';
    }
}