2021.12.03 BOJ 11660 구간 합 구하기 5

[출처: 백준 온라인 저지]

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

풀이

처음엔 그저 누적합으로 풀려고 하다 당연히 시간초과가 났다. 알고리즘 유형을 살펴보니 dp를 사용해야 한다는 것을 알았고, 테이블에서 x, y에 대하여 (1, 1) 부터 (x,y)까지의 합을 dp 2차원 배열에 넣기로 하였다. 0행과 0열의 dp값을 구하려면 인덱스 에러가 나기 때문에 dp 배열의 크기는 n+1로 설정하였다. 각 좌표 (x,+1 y+1)에 대하여 x행까지의 합과 y열까지의 합을 더해주고 겹치는 부분인 dp[x, y]을 빼주고 현재 좌표의 값인 matrix[x][y]의 값을 넣어주면 (1, 1)부터 (x,y)까지의 합을 구할 수 있다. 구하려는 값의 좌표인 x1, y1, x2, y2가 주어졌을 때 행으로 치면 x2부터 x1-1까지이고, 열로 치면 y2부터 y1-1이므로 dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]로 구현하였다.

import sys
input = lambda: sys.stdin.readline().rstrip()
n, m = map(int, input().split())
matrix = [list(map(int, input().split()))for _ in range(n)]
dp = [[0for _ in range(n+1)]for _ in range(n+1)]
for i in range(n):
  for j in range(n):
    dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + matrix[i][j]
for _ in range(m):
  x1, y1, x2, y2 = map(int, input().split())
  ans = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
  print(ans)