이제 구간 합 문제에 익숙해졌다고 생각했는데 아니었다.. 그래서 2차원 배열의 구간 합을 구하는 방법부터 공부했다.
2차원 구간 합
- 2차원 리스트에서도 마찬가지로 첫번째 원소부터 더한 값을 저장하면 된다.
- 그런데 (1, 1)부터 (x, y)까지의 모든 원소들의 합이 아니다.
- 행은 1부터 y까지, 열은 1부터 x까지의 원소들을 더한 값이다.
즉, 아래의 그림처럼 (1, 1)을 포함하는 사각형 안의 원소들의 합이다.
- 따라서 1차원의 구간 합 방식으로는 2차원 구간 합을 구할 수 없다. (2, 2)까지의 합은 (2, 1)까지의 합에 (2, 2)의 원소를 더한 값이 아니기 때문이다.
- 2차원 배열에서는 아래와 같은 방법으로 구한다고 한다.!
풀이
-
앞서 배웠던 방법으로 2차원 형식의 구간 합을 먼저 구한다.
-
그런데 그냥 DP[x][y] 값이 정답이 아니다. 구간 합은 항상 (1, 1)을 포함하는 사각형인데 문제에서 구하는 합들은 아래처럼 매우 다양하다.
-
그치만 어려운 것 없다. DP에 저장된 값들을 고려하여, 앞의 방법과 비슷하게 아래의 방법으로 빼주고 더해주면 된다.
코드
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
table = []
DP = []
for _ in range(N):
lst = list(map(int, input().split()))
table.append(lst)
#2차원 배열의 누적합 구하기
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] + table[i-1][j-1] - DP[i-1][j-1]
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
print(DP[x2][y2] - DP[x1-1][y2] - DP[x2][y1-1] + DP[x1-1][y1-1])- -1 때문에 인덱스 에러가 나지 않도록 배열은 0이 아닌 1부터 저장하도록 한다.
결과
재밌었던 문제 ㅎㅎ
