[백준] 11660. 구간 합 구하기 5 (파이썬)

🗂️   문제 

11660. 구간 합 구하기 5

---

---

📌   Point

Prefix Sum

2차원 배열 board의 누적합을 저장한 새로운 배열 prefix_sum을 만들어서 직사각형 구간의 합을 O(1)에 구할 수 있도록 한다.

 

 

---

📄   코드

def solution():
    N, M = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]

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

    for i in range(1, N+1):
        for j in range(1, N+1):
            prefix_sum[i][j] = (
                board[i-1][j-1] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1]
            )

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

solution()

---

✍🏻   풀이

시간 복잡도 : O(N^2 + M)

 

1. 누적합 배열 초기화
   
   • 1-based index 사용을 위해 prefix_sum을 (N+1) X (N+1)의 크기로 설정한다.
   • 인덱스 예외 처리를 줄인다.
2. 누적합 계산
   • prefix_sum[i][j] : (1, 1) 부터 (i, j) 까지의 부분합
   • 점화식
     • board[i-1][j-1] (* 현재 값) + 위쪽 누적합 + 왼쪽 누적합 - 겹치는 부분(왼쪽 위)을 다시 더한 것
3.  (x1, y1)부터 (x2, y2)까지 합
   • x1, y1, x2, y2 : 구간의 좌상단 (x1, y1), 우하단 (x2, y2)
   • 사각형 구간의 합을 누적합 배열을 이용해 O(1)로 계산
   • 겹치는 부분을 두 번 빼는 문제를 해결하기 위해 다시 더해준다.