[백준] 11660: 구간 합 구하기 2

4/28일부로 백준의 서비스가 종료됐다. ㅜㅜ

추후 문제만 볼 수 있는 사이트로 돌아온다고는 하지만 기간이 많이 남은 상태이므로,

Do it 알고리즘 코딩테스트 Python.의 책에 있는 문제들을 통해 정리해보겠다.

 

11660: 구간 합 구하기 2 (실버 1)

 

N × N개의 수가 N × N 크기의 표에 채워져 있다. 표 안의 수 중 (X, Y)에서 (X, Y)까지의 합을 구하려 한다. X는 행, Y는 열을 의미한다. 예를 들어 N = 4이고, 표가 다음과 같이 채워져 있을 때를 살펴보자. (2, 2)에서 (3, 4) 까지의 합을 구하면 3 + 4 + 5 + 4 + 5 + 6 = 27이고, (4, 4)에서 (4, 4)까지의 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때 이를 처리하는 프로그램을 작성하시오.

- 입력

1번째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다(1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000). 2번째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 4개의 정수 X, Y, X, Y가 주어지며, (X, Y)에서 (X, Y)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수다(X ≤ X, Y ≤ Y).

 

이 문제는 기존 1차원 배열의 구간 합에 이어 2차원 배열 형태에서 구간 합을 통해 해결하는 문제이다.이 문제에서는 누적 합/구간 합의 성질을 잘 이해하고 있으면 된다.

 

우선, 위의 2차원 배열을 누적합 형태로 만들어보자.

2차원에서는 특정 좌표 (x, y) 까지의 누적 합은 (1, 1)부터 (x, y)까지 사각형 범위의 합을 구하면 누적 합이 된다.

그림으로 표현해보면,

(2, 2) 좌표의 누적 합은 숫자 배열의 (1, 1) 부터 (2, 2)까지의 값들을 모두 더한 값이 된다. 

즉, (2, 2)의 누적 합 = (1, 1) + (1, 2) + (2, 1) + (2, 2) 이다.

이렇게 되면 이 누적 합 배열에서 특정 좌표만으로 해당 좌표까지의 범위 전체 값을 알 수 있다.

2차원 배열에서 누적 합을 구할 때는, 인덱스를 맞춰 쉽게 구분하기 위해 0열과 0행에 0으로 추가해준다.

이제 (1, 1) 부터 (4, 4)까지 순서대로 값을 채워나가는데

(1, 1)은 아래처럼 왼쪽과 위쪽의 1차원 배열의 합, 그리고 (1, 1)의 좌표를 더해서 구할 수 있다.

여기서 (0, 0)의 값이 겹치므로 해당 값을 한 번 빼주면 최종적으로 값이 나온다.

- 식

S[1][1] = S[0][1] + S[1][0] - S[0][0] + N[1][1]          S는 누적 합 배열, N은 원본 숫자 배열이다.

이 식은

S[row][col] = S[row-1][col] + S[row][col-1] - S[row-1][col-1] + N[row-1][col-1] 이 된다.

 

 

이제 이 누적 합 배열을 통해 구간 합을 구하면 된다.

기존 1차원 배열에서의 구간 합 식은 간단했다.

S[2] ~ S[5] 구간의 합을 구한다고 했을 때, S[5] - S[1] 을 하면 쉽게 구할 수 있었다.

 

2차원에서는 조금 달라진다.

S[2][2] ~ S[4][4] 구간의 합을 구한다고 했을 때,

왼쪽의 구간을 구해야하고, 그것은 곧 전체 구간에서 저 구간 외 나머지 구간들을 빼주면 된다는 뜻이다.

자 그럼 전체 구간을 구해보자.

이건 이미 누적 합을 통해 구해뒀기 때문에 S[4][4]가 전체 구간의 값이 된다.

 

다른 구간은 어떨까? 마찬가지로 누적 합 배열이 이미 완성되어 있기 때문에 좌표들을 통해 그 구간의 값을 바로 구할 수 있다.

우리가 필요한 구간은 (2, 4)와 (4, 2)이다.

이 두 개의 구간을 더하게 되면 겹치는 구간이 발생하는데(초록 구역), 이 구간의 값을 한 번 빼줌으로써 최종적으로 필요한 구간의 값을 구할 수 있다.

 

최종적으로 식은

result = S[4][4] - S[2][4] - S[4][2] + S[2][2] 가 된다.

 

 

import sys
input = sys.stdin.readline

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

maps = []

for _ in range(N):
    nums = list(map(int, input().split()))
    maps.append(nums)

prefix = [[0] * (N+1) for _ in range(N+1)]

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