[백준] 16507 : 어두운 건 무서워

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

16507번: 어두운 건 무서워

---

• 좌표를 입력받아서 그때그때 구간의 합을 다 구하기에는, 최대 1000 * 1000 * 10000 이 걸리므로 시간 초과가 날 듯 하다.
• 따라서 특정 직사각형 범위의 누적 합에 대해서 저장한 뒤, 인덱싱을 통해 적절히 연산할 수 있게 만들어 줄 수 있다.
• DP[r][c] 를 (1,1) ~ (r,c) 범위의 모든 값들의 합이라고 할 경우, 특정 좌표 사이의 직사각형을 구하는 것이 가능하다.
• 아래의 그림처럼 (2,1) ~ (3,4) 의 직사각형을 구하고 싶을 경우에는, 우선 전체 직사각형 넓이인 DP[3][4] 에서 DP[2][4](=y1) 직사각형과 DP[3][1](y=2) 직사각형 두개를 빼주고, DP[2][1] 은 앞서 빼준 두개 직사각형에서 공통으로 포함되었으므로 두번 빼준게 되니 다시 한번 더해주면 된다.

---

import sys

R, C, Q = map(int, input().split())
img = [[0]*(C+1)] + [[0]+list(map(int, input().split())) for i in range(R)]
dp = [[0 for c in range(C+1)] for r in range(R+1)]

for r in range(1, R+1):
    for c in range(1, C+1):
        dp[r][c] = dp[r-1][c]+dp[r][c-1]-dp[r-1][c-1]+img[r][c]     # dp[r][c] 는 1,1 부터 r,c 까지의 누적합

for line in sys.stdin:
    r1, c1, r2, c2 = map(int, line.split())                         # 모든 구간의 누적합을 알고 있으므로, 입력 받는 좌표들에 대해서 
    print((dp[r2][c2]+dp[r1-1][c1-1]-dp[r1-1][c2]-dp[r2][c1-1]) // ((r2-r1+1)*(c2-c1+1)))   # 해당 구간의 누적합을 구하기 위해, 포함되지 않는 직사각형을 잘라냄