[백준 / BOJ] C++ 16507 어두운 건 무서워

16507번: 어두운 건 무서워

 

문제

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

16507번: 어두운 건 무서워

 

 

풀이

[백준 / BOJ] C++ 11660 구간 합 구하기 5와 같은 문제다.

[백준 / BOJ] C++ 11660 구간 합 구하기 5

각 행별로 누적 합(prefix sum)을 만든 다음, 원하는 구간의 행별 구간 합을 모두 더하면 된다. q번 구간 합을 구하기 때문에 sum 변수 초기화에 신경 써줘야 하고, 공간의 개수는 (r2 - r1 + 1) * (c2 - c1 + 1) 임에 유의하자.

 

 

코드

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int r, c, q, r1, c1, r2, c2;
  cin >> r >> c >> q;
  int arr[1001][1001] = {0};
  for (int i = 1; i <= r; i++)
    for (int j = 1; j <= c; j++) {
      cin >> arr[i][j];
      arr[i][j] += arr[i][j - 1];
    }
  while (q--) {
    int sum = 0;
    cin >> r1 >> c1 >> r2 >> c2;
    for (int i = r1; i <= r2; i++)
      sum += arr[i][c2] - arr[i][c1 - 1];
    cout << sum / ((r2 - r1 + 1) * (c2 - c1 + 1)) << '\n';
  }
  return 0;
}