백준 - 16507 어두운 건 무서워

문제

2차원 배열이 주어질 때 일정 구간의 평균을 계산해라

생각

실버 문제에 1000 * 1000 크기?
들어오는 쿼리마다 배열돌면서 계산해주면 되겠다~ 했는데 시간 초과가 났다

(3%에서 틀렸습니다도 떴었는데, 정답 출력시 개행처리를 안 해줘서 그랬던 것!)

시간 초과 왜 날까 질문 검색 보고, 구글링하니까
배열의 최대 크기 1000 1000, 쿼리의 최대 개수 10000번
쿼리마다 뭘 해주면 1000 1000 * 10000 번 실행되니까 어마무시함

그래서 쿼리문 마다 뭔가 구해주지 말고
구간합 정보를 저장해놓고 나중에 물어보면 가져와서 계산하자! 라는 생각을 해야한댄다!!

구간합

2차원 배열에 0, 0 부터 i, j 위치까지의 합을 저장해놓고 사용!

값을 정해주는 법

왼편 합과 윗편 합을 합치면, 왼윗편 합이 중복되므로 그걸 빼주고 자신의 값을 더해줌!

sum[i + 1][j + 1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + num

한 값의 값을 아는 법

원본 값을 알라면, 원본까지의 합에서 왼편 윗편 빼주고 두 번 빼진 왼윗편 더해줘!
이렇게 하면 원본 값을 알 수 있으니까, 원본을 저장하는 배열이 필요 x

num = sum[i + 1][j + 1] - sum[i+1][j] - sum[i][j+1] + sum[i][j]

범위 합을 구하는 법

한 값 꺼내는 거랑 비슷하게 생각하면 됌

i1 ~ i2, j1 ~ j2 범위 합을 알고 싶으면
0 ~ i2, 0 ~ j2까지의 범위 합에서
0 ~ i1-1, 0 ~ j2와 0 ~ i2, 0 ~ j1-1 까지의 범위 합들을 빼주고,
두 번 빼진 0 ~ i1-1, 0 ~ j1-1 범위 합을 더해주면 됌!

tempSum = sum[i2][j2] - sum[i1-1][j2] - sum[i2][j1-1] + sum[i1-1][j1-1]

뭐 구간합 구한거를 범위 넓이 만큼 나눠주면 평균이지~~

코드

#include <iostream>
#include <string>

using namespace std;

long long pSum[1005][1005]; //0,0에서 i,j까지의 합을 구해놓고 저장

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

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

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			int num;
			cin >> num;
			pSum[i + 1][j + 1] = pSum[i][j + 1] + pSum[i + 1][j] - pSum[i][j] + num;
		}
	}

	for (int i = 0; i < q; i++) {
		int i1, j1, i2, j2;
		cin >> i1 >> j1 >> i2 >> j2;
		
		long long sum = pSum[i2][j2] - pSum[i1 - 1][j2] - pSum[i2][j1 - 1] + pSum[i1 - 1][j1 - 1];
		int cnt = ((i2 - i1 + 1) * (j2 - j1 + 1));

		cout << sum / cnt << "\n";
	}
	

	return 0;
}