백준 11660번: 구간 합 구하기 5

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

문제 접근

N × N 크기의 표에 수가 채워져 있고,
(x1, y1)부터 (x2, y2)까지의 직사각형 영역에 있는 수들의 합을 구하는 쿼리를 Q번 수행해야 한다.

해답 및 풀이

import sys
input = sys.stdin.readline

# 입력 받기
n, m = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]

# 누적합 배열 생성 (인덱스 편하게 하기 위해 +1 크기로 생성)
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] = (
            A[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)