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

 

 

 

 

 

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

---

<문제 출처> (SILVER Ⅰ)

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

16507번: 어두운 건 무서워

 

 

 

 

 

 

<풀이>

누적 합 문제이다.

2차원 배열의 누적 합을 구한 뒤,

Q로 주어진 (r1, c1), (r2, c2) 좌표의 누적합을 또 계산해야 한다.

계산된 값에 밝기 평균을 구해야 하니 좌표 안에 있는 사진 수로 나눠주면 된다.

(문제에서는 몫만 취하라고 하였다.)

 

 

 

 

 

 

 

<코드>

import sys
input = sys.stdin.readline

R, C, Q = map(int, input().split())

A = [[0] * (C + 1)]	# 원본 배열 초기 세팅
D = [[0] * (C + 1) for _ in range(R + 1)]	# 누적 합 배열 초기 세팅

# 원본 배열 추가
for _ in range(R):
    A_row = [0] + [int(x) for x in input().split()]
    A.append(A_row)

# 누적 합 배열 추가
for i in range(1, R + 1):
    for j in range(1, C + 1):
        D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j]

for _ in range(Q):
    r1, c1, r2, c2 = map(int, input().split())
    cnt = (r2 - r1 + 1) * (c2 - c1 + 1)	# cnt → 좌표 속 사진 수
    result = D[r2][c2] - D[r1 - 1][c2] - D[r2][c1 - 1] + D[r1 - 1][c1 - 1]
    print(result // cnt)	# 평균은 정수 나눗셈으로 몫만 취한다. (문제 조건)