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

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

공부 날짜 : 2023.02.02
정답 참조 여부 : x

사진에서 밝기가 주어질때 특정 구간 내에 밝기의 평균을 구하는 문제이다.

---

그냥 전형적인 2차원 누적합 문제 왜 실버 1인지 모르겠다..

주어진 데이터대로 2차원 누적합을 구하고 누적합으로부터 구간합을 구하되 추가적으로 r1,c1,r2,c2 영역의 넓이를 구해서 나눠주면 되는 문제다.

소스코드

import sys
input = sys.stdin.readline
###########################################
n, m, q = map(int, input().split())

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

sum_ = [[0 for _ in range(m+1)] for _ in range(n+1)]

# 누적합 구하기
for i in range(n):
    for j in range(m):
        sum_[i+1][j+1] = sum_[i][j+1] + sum_[i+1][j] - sum_[i][j] + picture[i][j]

# 요구사항 출력하기
for _ in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    
    # 평균을 구하기 위한 영역 구하기
    area = (r2 - r1 + 1) * (c2 - c1 + 1)
    
    # 누적합으로 구역합 구해서 영역을 나누기
    print((sum_[r2][c2] - sum_[r2][c1-1] - sum_[r1-1][c2] + sum_[r1-1][c1-1])//area)