[백준] 11660번 - 구간 합 구하기 5

---

문제 분석

먼저 질의의 개수가 100,000이므로 이 문제는 질의마다 합을 구하면 안 되고, 구간 합 배열을 이용해야 한다는 것을 알 수 있다.
구간 합 배열이 1차원에서 2차원으로 확장된 것으로 생각하여 구간 합 배열을 어떻게 구성하지 고민하는 것이 이 문제의 핵심이다.
2차원 구간 합 배열은 다음과 같이 정의할 수 있다.

2차원 구간 합 배열
sumArr[X][Y] = 원본 배열의 (0,0)부터 (X,Y)까지의 사각형 영역 안에 있는 수의 합

따라서 위의 내용에 따라 sumArr[X][Y]를 채우는 구간 합 공식을 떠올리면 다음과 같다

sumArr[X][Y] = sumArr[X][Y-1] + sumArr[X-1][Y] - sumArr[X-1][Y-1] + A[X][Y]

최종적으로 질의 X1,Y1,X2,Y2에 대한 답을 구간 합으로 구하는 방법은 아래와 같다.

sumArr[X2][Y2] - sumArr[X1-1][Y2] - sumArr[X2][Y1-1] + sumArr[X1-1][Y1-1]

---

소스 코드

# 구간 합 구하기5

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [[0]*(N+1)]
sumArr = [[0 for j in range(N+1)] for i in range(N+1)]

for i in range(N):
    numList = [0] + [int(x) for x in input().split()]
    arr.append(numList)

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

for _ in range(M):
    X1, Y1, X2, Y2 = map(int, input().split())
    print(sumArr[X2][Y2] - sumArr[X1-1][Y2] -
          sumArr[X2][Y1-1] + sumArr[X1-1][Y1-1])

---

마지막으로 이 문제를 풀면서 2차원 배열을 선언하는 방법에 대해서 다시 확인하게 되었다.
처음에 내가 쓴 방법대로 해보니 얕은 복사 방법이라 배열의 값을 하나만 수정해도 모든 2차원 배열에 값이 수정되는 오류를 확인하였다.
따라서 아래와 같은 방법으로 깊은 복사를 진행하여 2차원 배열을 올바르게 선언하여 오류를 해결하였다.