[백준][python] 구간 합 구하기5

문제

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

소스코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n,m = map(int,input().split())
    arr = [list(map(int,input().split())) for _ in range(n)]

    dp = [[0] * (n+1) for _ in range(n+1)]

    for i in range(1,n+1):
        for j in range(1,n+1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i-1][j-1]

    for k in range(m):
        x1,y1,x2,y2 = list(map(int,input().split()))
        
        print(dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1])

설명

1	2	3
2	3	4
3	4	5

(1,1) 부터 (2,3) 까지 합을 구하라면 (3+4+4+5) 을 더한 값이 최종 결과가 된다.

단순 반복문을 이용해서도 풀 수 있지만 시간초과 오류가 발생한다.

 

이런 문제는 구간 합으로 해결하면 된다.

 

prefix sum (구간 합)

구간 합은 어떤 수열에서 해당 인덱스까지 수열의 전체 합을 의미한다.

예를 들어 [10,20,30,40,50]의 구간합은 [10, 10+20, 10+20+30, 10+20+30+40,10+20+30+40+50] 으로 누적된 값이다.

 

이제 위의 2차원 배열을 구간 합을 이용해서 나타내면 아래와 같다.

1	1+2	1+2+3
1+2	1+2+2+3	1+2+2+3+3+4
1+2+3	1+2+2+2+3+3+4	1+2+2+3+3+3+4+4+5

 

위의 누적합에서 (2,2) ~ (3,3) 의 누적합을 구하려고 한다면 : 빨간색 섹션

전체 누적합에서 ((3,3) 의 값) 초록색 영역을 제거해준다 (1,3) 과 (3,1) 

그리고 초록색 중에 (1,1) 은 중복으로 제거됬으므로 한번 추가해준다.

그래서 최종 코드는 dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dx[x1-1][y1-1] 이 우리가 원하는 값이 된다.