11660번: 구간 합 구하기 5
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split()) # 표의 크기, 합을 구해야 하는 횟수
A = [] # NxN 리스트
for _ in range(n):
A.append(list(map(int, input().split())))
# 합 배열 D 구하기
D = [[0] * (n+1) for _ in range(n+1)] # DP 테이블
for i in range(1, n+1):
for j in range(1, n+1):
D[i][j] = D[i][j-1] + D[i-1][j] + D[i-1][j-1] + A[i][j] # 구간 합
# x1,y1에서 x2,y2까지의 합
for _ in range(m):
x1, y1, x2, y2 = map(int, input().split())
print(D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1])이 문제는 누적합 개념과 DP 개념을 함께 필요로 한다.
문제에서 주어진 예시인 (2, 2)에서 (3, 4)까지의 합은 (1, 1)에서 (3, 4)까지의 합 - 1행의 합 - 1열의 합 + (1, 1) 값과 같다.
이때 (1, 1)에서 (3, 4)까지의 합은 합 배열을 통해서 구해주어야 하는데 여기서 DP 테이블을 사용한다.
(2, 2)까지의 누적합을 구하는 과정을 보면 D[2][2] = D[1][2] + D[2][1] - D[1][1] + A[2][2]로 구할 수 있는데, 이를 일반화하면 (1, 1)에서 (i, j)까지의 합 D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]가 된다.
# 합 배열 D 구하기
D = [[0] * (n+1) for _ in range(n+1)] # DP 테이블
for i in range(1, n+1):
for j in range(1, n+1):
D[i][j] = D[i][j-1] + D[i-1][j] + D[i-1][j-1] + A[i][j] # 구간 합
위 식을 사용해 합 배열 D를 구했으니 (2, 2)에서 (3, 4)까지의 합은 D[3][4] - D[1][4] - D[3][1] + D[1][1]로 구할 수 있다.
이를 일반화하면 (x1, y1)에서 (x2, y2)까지의 합 = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]가 된다.
# x1,y1에서 x2,y2까지의 합
for _ in range(m):
x1, y1, x2, y2 = map(int, input().split())
print(D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1])
반응형