145. 11660(구간 합 구하기 5) - 파이썬

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

arr = [[0]*(N+1)] + [[0]+list(map(int,input().split())) for _ in range(N)]
result = ""

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

for _ in range(M):
  x1,y1,x2,y2 = map(int, input().split())
  tmp = 0
  
  tmp = arr[x2][y2] - arr[x2][y1-1] - arr[x1-1][y2] + arr[x1-1][y1-1]
  result += str(tmp) + "\n"

print(result)

문제요약

2차원 배열의 누적합을 구하라.

설명

 

1단계 누적합 구하기

예를 들어 (3,3) 의 합을 구하고 싶다고 하자.

먼저 (0,0) ~ (2,3) 의 합을 구한다 (1 + 2 + 3 + 2 + 3 + 4 = 15)

다음에는 (0,0) ~ (3,2) 의 합을 구한다 (1 + 2 + 2 + 3 + 3 + 4 = 15)

(0,0) ~ (2,2) 는 두번 더해주었기 때문에 한번 빼준다. (1 + 2 + 2 + 3 = 8)

 

따라서 (3,3)의 합은 5 + 15 + 15 - 8 = 27이된다.

 

이것을 누적합을 이용하여 적용해보면,

(3,3)의 누적합 = (3,3)의 값[5] + (2,3)의 누적합[15] + (3,2)의 누적합[15] - (2,2)의 누적합[8] 이라는 식을 만들 수 있다.

 

2단계 구간별 누적합 구하기

아래와 같이 (2, 2)부터 (3, 4)까지 합을 구하고 싶다고 하자.

 

그러면 (3,4)의 합에서

(3,4)의 합은 42

행이 1이고 열이 4까지의 합을 빼주고 (1 + 2 + 3 + 4 = 10)

행이 3이고 열이 1까지의 합을 빼준다. (1 + 2 + 3 = 6)

마지막으로 (1,1)의 합은 두번 빼주었으므로 한번 더해준다.

 

그러면 42 - 10 - 6 + 1 = 27 이 된다.

 

이를 누적합으로 구하면 

다음과 같이

(2,2) ~ (3,4)의 구간합 = (3,4)의 누적합[42] - (1,3)의 누적합[10] - (3,1)의 누적합[6] - (1,1)의 누적합[1]이라는 식을 만들 수 있다.

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

arr = [[0]*(N+1)] + [[0]+list(map(int,input().split())) for _ in range(N)]
result = ""

배열은 기본적으로 0부터 시작하니 [2][2] 가 진짜 [2][2]가 될 수 있도록 행이 0인 부분에는 전부 0을, 열이 0인 부분에도 전부 0을 저장한다.

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

각 부분에 부분합을 구해준다.

for _ in range(M):
  x1,y1,x2,y2 = map(int, input().split())
  tmp = 0
  
  tmp = arr[x2][y2] - arr[x2][y1-1] - arr[x1-1][y2] + arr[x1-1][y1-1]
  result += str(tmp) + "\n"

총 M번 진행될 것이다.

위에서 구한 누적합을 이용하여 2단계 식처럼 계산하여 tmp에 저장하고 result에 저장하여 한번에 출력해 줄 것이다.