https://www.acmicpc.net/problem/16507
시간 1초, 메모리 512MB
input :
- R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)
- 사진의 각 픽셀에는 밝기를 의미하는 정수 K (1 ≤ K ≤ 1,000)
- Q개의 각 줄에는 사진의 일부분을 나타내기 위한 두 꼭짓점을 의미하는 정수 r1, c1, r2, c2 (1 ≤ r1 ≤ r2 ≤ R, 1 ≤ c1 ≤ c2 ≤ C)
output :
- 직사각형의 밝기 평균을 출력한다. 평균은 정수 나눗셈으로 몫만 취한다.
드디어 성공한 문제... 최근에 수업 들으면서 누적 합을 자주 풀고 여러 번 복습을 하니
눈에 보였다.
개수를 따지는 것을 인덱스를 통해 처리하고, 그 외의 것은 dp 배열에 값을 저장해서 해결할 수 있다.
그리고 문제에서 이용하는 인덱스가 1부터 시작하니까 누적합도 그렇게 시작하도록 하자.
합을 구할 때는 data 배열의 인덱스를 따라간다고 보는 것이 더 편한 것 같다.
import sys
r, c, q = map(int, sys.stdin.readline().split())
data = []
for i in range(r):
temp = list(map(int, sys.stdin.readline().split()))
data.append(temp)
dp = [[0] * (c + 1) for i in range(r + 1)]
for x in range(r):
for y in range(c):
dp[x + 1][y + 1] = dp[x][y + 1] + dp[x + 1][y] - dp[x][y] + data[x][y]
for i in range(q):
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
temp = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]
num = (x2 - x1 + 1) * (y2 - y1 + 1)
print(temp // num)
