[백준] 11660번: 구간 합 구하기 5 - 2차원 구간 합 과정 설명

문제

https://www.acmicpc.net/problem/11660

풀이

구간 합 알고리즘을 활용한 풀이

왼쪽 표는 원본 배열에 왼쪽과 상단에 0을 추가한 배열이다.
오른쪽 표는 구간 합(dp)을 저장하는 배열이다.
오른쪽 표의 15는 왼쪽 표의 빨간색 구간의 합 이다.

15를 만들어 내기 위해서 기존에 만들어진 값을 사용하면
매번 왼쪽 표에서 이중 For문을 통해서 구하지 않아도 된다.

왼쪽 표에서 파란색 구간들의 합과
검은색 동그라미 즉, 해당 좌표의 값을 더하면 된다.

여기 끝이 아니다. 두 파란색 구간을 보면 겹친 부분이 있다.
즉, 이 구간은 두번 더해졌다는 의미이기 때문에 이 겹친 부분인 주황색 구간은 빼줘야 한다.

이것을 정리하면 다음과 같은 식이 나온다.
dp[row][col] = dp[row][col-1] + dp[row-1][col] + numbers[row][col] - dp[row-1][col-1]

이 과정을 반복하면 위와 같은 2차원 배열이 나온다.
각 좌표인의 값은 0,0 부터 해당 좌표 값까지의 직사각형 구간 합이다.

이제 시작점이 0,0 가 아닌 다른 좌표로 부터의 직사각형 구간 합을 구해보자.
범위는 (2,2) ~ (3,4) 로 하겠다.

(0,0) ~ (3,4) 구간 합(27)에서 주황 색 구간들의 합(6+6)을 뺀다.
이전과 마찬가지로 두번 빼지는 구간이 있다
따라서 이 구간의 합(1)을 한번 더해줘야 한다.
그럼 구하고자 하는 빨간색 구간의 합인 16(27 - 6 - 6 + 1)이 나온다.

이 식을 정리하면 다음과 같다.
answer = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

위 과정을 사용하여 푼 풀이이다.

import sys

input = sys.stdin.readline

N, M = map(int, input().split(" "))
numbers = [[0] * (N+1)] + [[0] + list(map(int, input().split(" "))) for _ in range(N)]
queries = [list(map(int, input().split(" "))) for _ in range(M)]


def solution(N, M, numbers, queries):
    dp = [[0] * (N+1) for _ in range(N+1)]

    for row in range(1, N+1):
        for col in range(1, N+1):
            dp[row][col] = dp[row][col-1] + dp[row-1][col] + numbers[row][col] - dp[row-1][col-1]

    for query in queries:
        x1, y1, x2, y2 = query
        print(dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1])
    return


solution(N, M, numbers, queries)