구간 합 구하기 5 실버1 (백준, DP)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]
sum_data = [[0] * (n+1) for i in range(n+1)]

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

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())

    print(sum_data[x2][y2] - sum_data[x1-1][y2] - sum_data[x2][y1-1] + sum_data[x1-1][y1-1])

 

---

문제 풀이 : 

 

이번 문제는 x1, y1, x2, y2까지 배열을 모두 다 더한 값을 돌려주면 되는데 좌표를 받을 때마다 계산을 하면 당연하게도 시간초과가 걸린다.

 

여기서 사용가능한것이 누적합이다.

 

누적합이란 이전 값들을 다 더한 경우를 보면 된다.

 

예를 들어 [1,2,3,4,5]라는 데이터가 들어왔다고 하자.

 

그러면 누적합은 [1, 3, 6, 10, 15]가 저장이 된다.

 

만약 3 ~ 5까지 합을 구해달라고하면 3, 4, 5를 더하면 되는 간단한 문제이지만 만약 데이터가 수천 수억개가 된다고 생각해보자. 그러면 매번 수천 수억번의 연산이 이루어져야 답을 가져올 수 있다.

(물론 그것보단 적게 걸리겠지만..)

 

누적합에서 1차원일경우 3과 5 사이의 합을 구해라라고 하면 누적합 5에서 누적합 2를 뺀 15 - 3 = 12가 바로 나오게된다.

---

지금까지 누적합이 어떤 것인지 보았고 이번 문제에서는 2차원 누적합을 진행하게 된다.

 

2차원의 경우 2가지 방법이 존재하는데 말만 들었을 때 애매할 수 있으므로 밑의 그림을 가지고 이해해보자.

(나는 2번 방법을 택했다.)

1. 1행 1열 -> 1행 2열 -> .... 1행 n열까지 더한 후 해당 값을 가지고 2행 1열 -> 2행 2열 이렇게 가는 경우
2. 1행 1열 -> 1행 2열 -> ... 1행 n열까지 행의 값을 더한 후 2행 1열에서는 1행 1열값과 2행 1열값을 더하는 형식이다.

위의 그림을 보면 조금 더 이해가 쉬울 수 있다.

 

그러면 위와 같은 누적합을 만드는 알고리즘을 생각해보면 다음과 같이 생각 할 수 있다.

 

편의상 데이터가 들어있는 리스트 이름을 data

누적합 데이터가 들어있는 리스트 이름을 sum_data라고 하겠습니다.

 

그리고 계산을 편하게 하기 위해서 누적합에는 데이터 행 수 +1, 열 수 +1을 진행하고 미리 0의 데이터를 넣어 놓았습니다. 실제 그림을 보면 다음과 같습니다. (1행과 1열은 사용을 안하게됩니다.)

함수로 보면 다음과 같이 만들 수 있습니다.

sum_data [ i ] [ j ] = sum_data [ i ] [ j - 1 ] + sum_data[ i - 1 ] [ j ] - sum_data[ i -1 ][ j - 1 ] + data [ i ] [ j ]

 

진행하는 과정을 그림을 보면서 보겠습니다.

---

1. X1, Y1의 누적합을 구하려고 합니다. 위치는 다음과 같습니다.

 

---

2. 여기에서 이미 계산이 되어져있는 X1, Y1-1을 먼저 더합니다.

---

3. 두번째로 이미 계산되어 있는 X1-1, Y1도 더합니다.

---

4. 이렇게되면 한가지 문제가 발생하는데 X1-1, Y1-1의 값이 공통적으로 2번 더해지게 됩니다. 그래서 해당값은 빼줍니다.

그리고 마지막으로 X1, Y1에 있는 Data값을 가져오게되면 해당 누적합이 나오게 됩니다.

 

이 방식으로 누적합을 구하게 되었고 누적합을 구하는 방식과 동일하게 이번 문제를 풀면 됩니다.

 

---

문제에 주어진것을 풀어봅시다.

 

1. X1, Y1, X2, Y2의 값이 주어지므로 다음과 같이 그림을 그릴 수 있습니다.

 

---

2. 이번 문제에서 구하고 싶은것은 해당 값에 있는 모든 합입니다. 그러면 X2, Y2에 있는 최종합에서 필요없는부분을 제거해주면 됩니다.

누적합과 구하는 방식이 비슷하지만 이미 구해진 값에서 빼는것과 X Y의 값을 신경써주면서 구하면 됩니다.

 

sum_data[x2][y2] - sum_data[x1-1][y2] - sum_data[x2][y1-1] + sum_data[x1-1][y1-1]

 

마지막으로 해당 값을 출력해주면 답이 나오게됩니다.

 

누적합배열을 사용하는 것에 안좋은 점은 수정이 일어나는 경우에선 사용하기 힘들다는 점이다.

 

만약 변경이 필요한 경우 세그먼트 트리 혹은 펜윅 트리를 사용해야한다.

 

 

https://pacific-ocean.tistory.com/228

[백준] 1541번(python 파이썬)