[BOJ 2167] 2차원 배열의 합

문제

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

입력

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).

출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

예제 입력 1 복사

2 3
1 2 4
8 16 32
3
1 1 2 3
1 2 1 2
1 3 2 3

예제 출력 1 복사

63
2
36

 

 

시간복잡도를 고려했을때 이 문제는 각 보드를 형성하고 모든 경우의 수를 계산 하는경우 시간초과가 걸린다. 따라서 누적 합(구간 합)의 개념을 이용한다. 이 알고리즘을 활용하려면 먼저 합배열을 구해야한다. 

 

합 배열의 정의

S[i] = A[0] + A[1] + ... + A[i-1] + A[i] # A[0] 부터 A[i] 까지의 합

 

합 배열을 구하는 방법

S[i] = A[i] + S[i-1]

 

1차원 배열의 구간합 구하기

import sys
prifx_sum = [0] # 배열의 시작을 1부터 하기 위해 0을 추가하여 맞춰준다.
numbers = list(map(int, input()) # 합 배열을 만들 수열
temp = 0

for i in numbers:
	temp += i 
    prifix_sum.append(temp)

2차원 배열의 구간합 구하기

 

손으로 먼저 그려서 계산해보면 다음과 같은 식을 얻을 수 있다. 이를 코드로 구현한다.

 

## 2차원 배열의 구간합 구하기

import sys

n, m = map(int, input().split()) # n행 m열

# board 배열
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 누적 합 배열 초기화
prefix_sum = [[0] * (m + 1) for _ in range(n + 1)]

# 누적 합 배열 계산
for i in range(1, n + 1):
    for j in range(1, m + 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]

누적 합은 배열의 각 위치에서 그 위치까지의 합을 미리 계산해 놓은 것입니다. 이렇게 하면 각 쿼리를 상수 시간에 처리할 수 있다. 2차원 배열에서 누적 합을 사용하는 경우에는, 배열의 (i, j) 위치에 대해 (1, 1)부터 (i, j)까지의 부분 배열의 합을 저장합니다. 이를 이용하면, 주어진 범위의 부분 배열의 합을 O(1) 시간에 구할 수 있다.

 

이렇게 누적합에 대한 배열을 구한 후 2차원 배열에 대한 합을 구하면 다음과 같다.

t = int(input())
for _ in range(t):
    i, j, x, y = map(int, sys.stdin.readline().split())
    answer = prefix_sum[x][y] - prefix_sum[i-1][y] - prefix_sum[x][j-1] + prefix_sum[i-1][j-1]
    print(answer)