[백준/파이썬] 11660번: 구간 합 구하기 5

문제

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

풀이

• N x N 크기의 표
• (x1, y1) ~ (x2,y2)까지 합

  ex)
  
  (2,2)부터 (3,4)까지의 합
  -> 3+4+5+4+5+6 = 27
  (4,4)부터 (4,4)까지의 합
  -> 7

2차원 배열에서의 누적합 문제입니다.

위에 있는 예제를 안 봤다면 아마 (2,2)부터 (3,4)의 합을 3+4+5+3+4+5+6으로 풀었을 것 같네요..(사실 처음에 그렇게 풀었읍니다..)

일단 누적합을 저장할 배열을 선언해줍니다.
이때 문제에서 배열의 시작이 (0,0)이 아닌 (1,1)이므로 n+1로 선언하였습니다.

num = [[0] * (n+1) for _ in range(n+1)]

후에 (1,1)부터 누적합 값을 추가해주겠습니다.
이때 num[i][j]는 시작 지점부터 (i,j)의 모든 값을 추가하는 것이 아닌 배열에서 본인 + num[i-1][j] + num[i][j-1]을 추가한 후, num[i-1][j-1]을 빼줘야 합니다.

예를 들어, (3,3) 값을 추가해보겠습니다.

(3,3)의 누적합은 (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)입니다.

• 이걸 누적합을 이용하여 풀면,

1. (1,1)+(1,2)+(2,1)+(2,2)+(3,1)+(3,2)
   즉, num[3][2]와
2. (1,1)+(1,2)+(1,3)+(2,1)+(2,2)+(2,3)
   즉, num[2][3]을 더한 후
3. 여기서 중복되는 값인 (1,1)+(1,2)+(2,1)+(2,2)
   즉, num[2][2]를 빼주면
4. (1,1)+(1,2)+(1,3)+(2,1)+(2,2)+(2,3)+(3,1)+(3,2)을 얻을 수 있습니다.
5. 마지막으로 본인인 (3,3)을 더해주면 원하는 값을 구할 수 있게 됩니다.

점화식으로 작성하게 되면 num[i][j] = arr[i-1][j-1] + num[i-1][j] + num[i][j-1] - num[i-1][j-1]가 됩니다.

for i in range(1,n+1):
    for j in range(1,n+1):
        num[i][j] = arr[i-1][j-1] + num[i-1][j] + num[i][j-1] - num[i-1][j-1]

같은 방식으로 우리가 원하는 구간의 합을 구하려면
num[x2][y2]에서 num[x1-1][y2]와 num[x2][y1-1]를 뺀 후, 중복하여 제거된 num[x1-1][y1-1])를 더해주면 됩니다.(x1 < x2, y1 < y2)

코드

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]

num = [[0] * (n+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        num[i][j] = arr[i-1][j-1] + num[i-1][j] + num[i][j-1] - num[i-1][j-1]

for _ in range(m):
    x1,y1,x2,y2 = map(int,input().split())
    print(num[x2][y2] - num[x1-1][y2] - num[x2][y1-1] + num[x1-1][y1-1])