[n16507] 어두운 건 무서워 - python

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

16507번: 어두운 건 무서워

---

(처음 든 생각)

이건 무조건 완탐으로 풀면 안된다는 거..?

시간초과가 뜰 것 같았다.

 

근데 도저히 방법이 떠오르지 않아서 힌트를 보니

누적합 문제라고 한다..

 

누적합 문제 1차원 배열로는 풀어봤으나,

2차원 배열로 풀어본 기억은 없는 것 같다.

 

그래서 개념 정리부터 싹 하고 왔다!

 

---

(누적합, 구간합 개념 정리)

구해야 하는 건 빨간 영역의 합

A : 파란색 

B : 초록색

C : 주황색

D : 검정색 (제일 큰 영역)

 

빨간 영역 = D-A-B+C

(C를 더해주는 이유는 A와 B를 빼면서 C 영역을 2번 빼줬기 때문이다)

 

 

위 예시에 나온대로 구간합을 구해줄 예정!

구간합을 그냥 1차원 배열처럼 좌->우로 가며 더해주는 줄 알았는데

그게 절대 아니었따..

위 방식대로 하다 시간 허비하고,

다시 알아보니까 2차원 배열은 행, 열 모두를 처리해줘야 한다고 함!

 

위 예제를 토대로 2차원 배열을 작성하면 아래와 같다.

(0행, 0열은 인덱스 에러를 방지하기 위하여 추가해주었다.)

0	0	0	0	0	0	0
0	4	1	3	4	9	5
0	1	2	8	7	5	5
0	1	5	3	4	2	5
0	5	2	1	2	3	5
0	5	2	1	2	3	5

 

위 배열을 구간합 배열로 바꿔줄 예정!

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + array[j-1]

>> 사실 이 식을 매번 반복해주면 된다.

 

그래도 나중에 헷갈릴 경우를 대비하여 자세히 풀어쓰기!

---

(1,2)와 (2,1)에는 이미 누적합이 들어가있는 상태라고 가정한다.

(1,1 = 4)   (1,2 = 5)

(2,1 = 5)    (2,2)

위와 같은 경우 (2,2)에 들어가야 할 값을 구해보자!

그러려면 (2,1) + (1,2) - (1,1) + (2,2)를 해주면 된다!

 

(2,1) => (1,1) + (2,1) = 5

(1,2) => (1,1) + (1,2) = 5

(2,2) = (1,1) + (1,2) + (2,1) + (2,2) 가 되어야 한다.

근데 우리는 기존 배열의 값이 아닌 누적합으로 계산을 해줄 예정이니까

(2,1)과 (1,2)에는 (1,1) 값이 둘 다 들어가 있는 상태

따라서 (2,2)를 구할땐 2번 들어가있는 (1,1)을 한 번 빼줘야한다.

 

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + array[j-1]

---

(풀이)

r, c, q = map(int, input().split())
dp = [[0 for _ in range(c + 1)] for _ in range(r + 1)]

for i in range(1, r + 1):
    array = list(map(int, input().split()))
    for j in range(1, c + 1):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + array[j-1]

for i in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    rect_sum=dp[r2][c2]-dp[r2][c1-1]-dp[r1-1][c2]+dp[r1-1][c1-1]
    row=r2-r1+1
    col=c2-c1+1
    answer=rect_sum//(row*col)
    print(answer)

---