[Python/파이썬] 백준 16507번 어두운 건 무서워

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

코드

import sys
input = sys.stdin.readline

r, c, q = map(int, input().split())
picture = [list(map(int, input().split())) for _ in range(r)]

# 누적합 구하기
acc = [[0]*(c+1) for _ in range(r+1)]
for i in range(r):
    for j in range(c):
        acc[i+1][j+1] = acc[i][j+1] + acc[i+1][j] - acc[i][j] + picture[i][j]

for _ in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    light_sum = (acc[r2][c2] - acc[r1-1][c2] -
                 acc[r2][c1-1] + acc[r1-1][c1-1])//((r2-r1+1)*(c2-c1+1))
    print(light_sum)

 

해당 문제는 누적합을 이용하여 풀 수 있다. (r1, c1)과 (r2, c2)를 꼭지점으로 하는 직사각형의 밝기 평균을 구하려면 이중 for문을 돌아야 하는데 매번 이 과정을 반복한다면 시간 복잡도가 커질 수 밖에 없다. 그렇지만 누적합을 미리 한 번만 구해둔다면 매번 이중 for문을 돌 필요 없이 사칙연산만으로 직사각형의 밝기 평균을 구할 수 있기 때문에 시간 복잡도를 크게 낮출 수 있다.