구간 합 구하기 5

파란색 구간이 구해야하는 구한 합이라면 빨간색 부분과 초록색 부분을 제외하면 된다고 생각

시도1

맨 처음에 가로 구간합, 세로 구간합으로 나눠서 구했음. 

 

(파란색 구간의 누적합 - (빨간색 누적합 + 주황색 누적합 + 빨,주 겹치는 부분)) 으로 구하면 될 줄 알았다

근데 그림에서도 보이다시피 파란색에 끝부분과 주화색 끝 부분도 계산식에 포함돼서 결과가 제대로 나오지 않음

빨간색 점선 부분도 포함

 

시도2

저 양쪽 끝을 포함하지 않도록 하기 위해 행별로 누적합을 구하기로 했다.

코드

import sys

n, m = map(int, input().split())

data = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

#가로형태?로 누적합 구한것
sum_col = [[0] * (n+1) for _ in range(n+1)]

#x1, y1 ~ x1~ y2 / x2, y2 ~ x2, y2
sum_col[1][1] = data[1][1] #초기값 세팅

for i in range(1, n+1):#row
  for j in range(1, n+1):#col
    # if i == 1 and j == 1: #[0][0]이면 누적합이 본인
    #   sum_col[i][j] = data[i-1][j-1]
    if j == 1: #다음 행으로 이동하면 그 행부터 다시 누적합
      sum_col[i][j] = data[i-1][j-1]
    else:
      sum_col[i][j] = data[i-1][j-1] + sum_col[i][j-1]

for i in range(m):
  x1, y1, x2, y2 = map(int, input().split())
  sum = 0#파란색 박스
  for j in range(1, x2+1): # (x2,y2) 까지 누적합 구하기
    sum += sum_col[j][y2]
  
  box1 = 0 # 주황색 박스
  for j in range(1, x1):
    box1 += sum_col[j][y2]

  box2 = 0 #빨간색 박스
  for j in range(1, x2+1):
    box2 += sum_col[j][y1-1]
 
  overlap_box = 0 #겹치는 박스
  for j in range(1, x1):
    overlap_box += sum_col[j][y1-1]

  print(sum - (box1+box2-overlap_box))

 

시간초과: 원인은 m=100,000이고 x1 = 1000만 되어도 시간초과

 

시도3

생각해보면 빨간색과 주황색을 모두 구할 필요가 없다. 입력으로 주어진 x1, y1 ~ x2, y2구간만 고려하면 됨

코드

import sys

n, m = map(int, input().split())

data = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

#가로형태?로 누적합 구한것
data_sum = [[0] * (n+1) for _ in range(n+1)]

#x1, y1 ~ x1~ y2 / x2, y2 ~ x2, y2
data_sum[1][1] = data[1][1] #초기값 세팅

for i in range(1, n+1):#row
  for j in range(1, n+1):#col

    if j == 1: #다음 행으로 이동하면 그 행부터 다시 누적합
      data_sum[i][j] = data[i-1][j-1]
    else:
      data_sum[i][j] = data[i-1][j-1] + data_sum[i][j-1]

for i in range(m):
  x1, y1, x2, y2 = map(int, input().split())
  box1 = 0
  for i in range(x1, x2+1):
    box1 += data_sum[i][y2]

  box2 = 0
  for i in range(x1, x2+1):
    box2 += data_sum[i][y1-1]
  
  print(box1-box2)