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

문제 링크

16507번: 어두운 건 무서워

 

풀이

누적합 문제

1. 사진의 밝기를 입력받으며, 각 행마다 누적합을 구한다.
2. func를 통해 영역의 사진 밝기 평균을 구하는데, 각 행열은 1부터 시작하므로 -1 해준다.
   1. r1부터 r2까지 행마다 c2에서 c1-1의 값을 빼주면 해당 행의 영역 값을 구할 수 있다.
   2. c1이 0이라면 c1-1에서 에러가 나니까 예외 처리를 해준다.
3. 사각형의 영역값으로 sum을 나눠주면 된다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

int func(vector<vector<int>> &arr, int r1, int c1, int r2, int c2)
{
    int sum = 0;
    for (int i = r1; i <= r2; i++)
    {
        if (c1 == 0) sum += arr[i][c2];
        else sum += arr[i][c2] - arr[i][c1-1];
    }
    return sum / ((c2 - c1 + 1) * (r2 - r1 + 1));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int r, c, q;
    cin >> r >> c >> q;

    vector<vector<int>> arr(r, vector<int>(c));
    for (int i = 0; i < r; i++)
    {
        int sum = 0;
        for (int j = 0; j < c; j++)
        {
            int tmp;
            cin >> tmp;
            sum += tmp;
            arr[i][j] = sum;
        }
    }

    for (int i = 0; i < q; i++)
    {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << func(arr, r1 - 1, c1 - 1, r2 - 1, c2 - 1) << '\n';
    }
}