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

---

접근 방법

 

단순히 숫자들을 이차원 배열로 받아 입력 케이스마다 합을 구하는 것은 시간이 많이 소요될 것이라 생각했고

누적합을 이용하기로 했다.

배열을 행을 기준으로 누적합으로 만들어놓고 케이스에 따라 뺄셈만 하여 합을 구한다

---

풀이

 

행을 기준으로 x행은 원래 x행의 수와 x-1행의 수를 더해갔다

 

이후 각 케이스에 따라 각 열마다

처음 시작 행이 1일 경우와 1이 아닌, 중간부터 합을 구하는 경우로 나누어 계산했다.

if x1 == 1:
  sum += arr[x2 - 1][j]
else:
  sum += arr[x2 - 1][j] - arr[x1 - 2][j]

---

정답 코드

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
arr = [[0 for i in range(n)]] * n
for i in range(n):
  arr[i] = list(map(int, input().split()))
for i in range(1, n):
  for j in range(n):
    arr[i][j] += arr[i - 1][j]

for i in range(m):
  sum = 0
  x1, y1, x2, y2 = map(int, input().split())
  for j in range(y1 - 1, y2):
    if x1 == 1:
      sum += arr[x2 - 1][j]
    else:
      sum += arr[x2 - 1][j] - arr[x1 - 2][j]
  print(sum)

---

오답 풀이

케이스마다 합을 구하는 과정에서 행과열, x와y, [i][j]를 계속 헷갈려서 x와y를 반대로 대입했었다.