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

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

16507번: 어두운 건 무서워

 

문제분석

1. 분류
   • 누적 합
2. 문제설명
   • R x C 크기의 사진이 주어질 때, 사진의 일부분에 해당하는 밝기 평균을 구한다.
   • 입력: 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C(1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q(1 ≤ Q ≤ 10,000)가 주어진다.
   • 다음 R개의 줄에 걸쳐 R x C 크기의 사진 정보가 주어지고, 사진의 각 픽셀에는 밝기를 의미하는 정수 K가 주어진다.
   • 다음 Q개의 각 줄에는 사진의 일부분을 나타내기 위한 두 꼭짓점을 의미하는 정수 r1, c1, r2, c2 (1 ≤ r1 ≤ r2 ≤ R, 1 ≤ c1 ≤ c2 ≤ C)가 주어진다.
   • 출력: Q개의 각 줄에 주어진 사진에서 두 점 (r1, c1)과 (r2, c2)를 꼭짓점으로 하는 직사각형의 밝기 평균을 출력한다. 평균은 정수 나눗셈으로 몫만 취한다.

 

코드

1	R, C, Q = map(int, input().split())
2	picture = [list(map(int, input().split())) for _ in range(R)]
3	dp = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
4
5	for i in range(1, R + 1):
6	for j in range(1, C + 1):
7	dp[i][j] = -dp[i-1][j-1] + dp[i-1][j] + dp[i][j-1] + picture[i-1][j-1]       #(1, 1) ~ (i, j)의  밝기 합
8
9	for i in range(Q):
10	r1, c1, r2, c2 =  map(int, input().split())
11	ans = dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1] + dp[r1-1][c1-1]      #(r1, c1) ~ (r2, c2)의 밝기 누적합
12	num = ((r2 - r1) + 1) * ((c2 - c1) + 1)        #구간에 속하는 픽셀의 개수
13	print(ans // num)

 

문제풀이

• (1, 1)부터 (i, j)까지의 합을 구해 dp[i][j]에 저장해두고, 그것을 활용해 구간의 합을 구한다.