누적합 | 백준 11660 구간 합 구하기 5

문제

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

수가 채워져있는 NxN크기의 표가 있을 때 (x1, y1)부터 (x2, y2)까지의 합을 구하여라.

 

풀이

 

처음에 생각했던 방식

1. 각 행의 누적합을 구해놓고

2. (x1, y1)부터 (x2, y2)까지 합을 구할 때 x1행부터 x2행까지 반복하면서

3. i행의 y2열까지의 누적합 - i행의 y1-1까지의 누적합을 계산하려고 했음

 -> 시간 초과. 직사각형 영역 전체의 누적합을 구해놓고 계산해야 함. 

 

(아래는 틀린 코드)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

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

#각 행의 누적합 계산
for i in range(1, N+1):
    for j in range(1, N+1):
        prefix[i][j] = arr[i-1][j-1] + prefix[i][j-1]

for _ in range(M):
    result = 0
    x1, y1, x2, y2 = map(int, input().split())
    for k in range(x1, x2+1):
        result += (prefix[k][y2] - prefix[k][y1-1])
    print(result)

 

 

옳은 방식

1. 모든 영역에 대한 누적합을 구한다.

(1) 현재 영역

(2) + 현재 영역의 위쪽 영역 전체 

(3) + 현재 영역의 왼쪽 영역 전체 

(4) - 겹치는 영역

for i in range(1, N+1):
    for j in range(1, N+1):
        # prefix[i][j] = 현재 영역 + 현재 영역의 위쪽 영역 전체 + 현재 영역의 왼쪽 영역 전체 - 겹치는 영역
        prefix[i][j] = arr[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

 

2. 구간합을 구한다.

(1) prefix[x2][y2]

 

 

(x2, y2)까지의 누적합 = prefix[x2][y2]

여기에서 필요없는 부분을 빼야 한다.

(2,2)에서 (3,4)까지의 합을 구한다고 가정하자.

prefix[3][4]는 왼쪽의 사진과 같다.

 

 

 

 

 

(2) - prefix[x1-1][y2] - prefix[x2][y1-1] 

 

 

 

따라서  (2,2)에서 (3,4)에 포함되지 않는 영역인 빨간 박스 영역을 빼준다.

그런데 중복으로 제거되는 부분이 발생한다.

 

 

 

 

 

(3) + prefix[x1-1][y1-1]

 

 

 

따라서 파란 박스 부분을 더해준다.

 

 

 

 

 

 

 

작성한 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(1, N+1):
    for j in range(1, N+1):
        # prefix[i][j] = 현재 영역 + 현재 영역의 위쪽 영역 전체 + 현재 영역의 왼쪽 영역 전체 - 겹치는 영역
        prefix[i][j] = arr[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    result = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]
    print(result)