[ baekjoon ] 구간 합 구하기 5 11660번 ( python )

문제

백준 11660 구간 합 구하기 5 풀이 ( 파이썬 )

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

11660번: 구간 합 구하기 5

 

풀이

2차원 누적합을 저장했다가 구해야 하는데 2차원 누적합을 저장하는 방법은

주황색 부분의 누적합을 구한다고 했을 때

일단 주황 부분의 값과 초록색과 파란색의 누적합을 더하고 노란색의 누적합을 빼주면 된다. 왜냐면 초록색 누적합을 계산할 때와 파란색 누적합을 계산할 때 모두 노란색이 포함되므로 중복값을 빼주는 것이다.

그렇다면 식은

pre_sum[i][j] = pre_sum[i][j - 1] + pre_sum[i - 1][j] + graph[i - 1][j - 1] - pre_sum[i - 1][j - 1]

이렇게 나오게 된다 이렇게 구한 누적합을 저장한 2차원 배열은

이렇게 만들어진다. 여기서 왼쪽와 위의 값을 0으로 한 줄씩 추가한 이유는 맨 왼쪽과 맨 오른쪽 값을 각각 왼쪽과 오른쪽의 영향을 받지 않기 때문이다.

 

이제 답을 찾기 위해 예를 들어 주황색 부분의 합을 구하고 싶다면

64를 가리키는 누적합에서 초록색과 파란색을 빼고 노란색을 더한다 노란색을 더하는 이유는 위의 누적합을 구할 때랑 같은 이유이다.

전체 코드를 보면

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))

pre_sum = [[0] * (n + 1) for _ in range(n +  1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        pre_sum[i][j] = pre_sum[i][j - 1] + pre_sum[i - 1][j] + graph[i - 1][j - 1] - pre_sum[i - 1][j - 1]

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