[백준] 11660번 구간 합 구하기 5 파이썬 코드

코드

# O(N^2+M)으로 해결할 수 있어야 한다
# O(N^2)인 이유는 2차원 배열의 구간합을 계산해야하므로

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
numlst = [[0]*(n+1)] # 리스트 인덱스 1로 맞춰주기 위함
for _ in range(n):
  numlst.append([0,*map(int, input().split())])
arr_sum = [[0]*(n+1) for _ in range(n+1)]

for i in range(1,n+1):
  for j in range(1,n+1):
    arr_sum[i][j] = numlst[i][j] # 구간합을 구해줄 자리에 더해줘야할 값 할당
    arr_sum[i][j] += arr_sum[i][j-1] # 행 구간 합 더해주기
    arr_sum[i][j] += arr_sum[i-1][j] # 열 구간합 더해주기
    arr_sum[i][j] -= arr_sum[i-1][j-1] # 겹치는 부분 빼주기

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

2차원 배열의 구간합 구하는 것이 정확히 무엇인지 몰라서 시간을 많이 쓴 문제. 그래도 이번 기회에 이차원 배열에서의 구간합이 무엇인지 알게 되었다. 잊기 전에 따로 구간합에 대해서 포스팅을 해야겠다.