[백준/python] 11660 구간 합 구하기 5 - DP 누적합 사용하기 (다이나믹 프로그래밍)

#11660 구간 합 구하기
import sys
N, M = map(int, sys.stdin.readline().split())

matrix = []
for _ in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    matrix.append(row)

for _ in range(M):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    total = 0
    for row in range(x1-1, x2):
        for col in range(y1-1, y2):
            total += matrix[row][col]
    print(total)

 

그래 그럴줄 알았어 만만하게 합격 줄리가 없지. 시간초과

 

그러면 어떻게 풀어야해?

DP 다이나믹 프로그래밍, 누적합을 사용해야한다.

다이나믹 프로그래밍(DP)란?

큰 문제를 작은 문제의 결과를 재사용해서 효율적으로 푸는 방법
큰 문제를 작은 문제로 쪼개서 푼다라고 생각하면 됨.

누적합이란?

2차원 배열 (행렬)의 특정 구간 합을 빠르게 구하기 위한 전처리 방식

 

내가그린기린그림

 

이해가 잘 안가서 그림으로 그려왔다.

내가 [0][0]부터 [3][3]까지의 합 S[3][3]을 구하고싶다면,

S[3][3] = a[3][3] + S[3][2] +  S[2][3]  - S[2][2]를 하면 되는것이다.

 

이것을 식으로 일반화 해보면,

S[i][i] = a[i][i] + S[i][i-1] + S[i-1][i] - S[i-1][i-1]이 되겠지.

이것을 적용해서 풀면된다.

total = matrix[x][y] + DP[x-1][y] + DP[x][y-1]- DP[x-1][y-1]

 

그래서 나는 코드를 이렇게 짰다.

자, 그럼 여기서 나같은 사람은 또 의문이 생길것이다.

위는 (0,0)부터 시작하는 코드잖아!!!!!

중간에서 부터 시작하는건 다시 계산해야하는거 아냐?

맞다.

저렇게 중간부터 시작하는 합을 구하려면,

이렇게 큰 사각형에서 빼줘야한다.

그런데! 이것도 위의 DP 식을 사용하면 된다는점~!

(x1, y1)부터 (x2, y2)까지 구한다고 하면,

total = DP[x2][y2]- DP[x2][y1-1] - DP[x1-1][y2] + DP[x1-1][y1-1]

 

이렇게 해주면 된다!

 

그러면 이렇게 짜본 코드는?

import sys
N, M = map(int, sys.stdin.readline().split())

matrix = []
DP = [[0] * (N+1) for _ in range(N+1)]

for _ in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    matrix.append(row)

for i in range(N+1):
    for j in range(N+1):
        DP[i][j] = matrix[i-1][j-1] + DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1]

for _ in range(M):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    total = DP[x2][y2] - DP[x1-1][y2]- DP[x2][y1-1] + DP[x1-1][y1-1]
    print(total)