[JAVA] 구간 합 구하기 5 ::: DP, 누적 합

[ 문제 ]

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

 

 

 

[ 제출코드 ]

 

 

 

[ 풀이 ]

2차원 배열에서 각 부분까지의 누적합을 구한 뒤 계산합니다.

 

아래 배열(arr)이 주어졌을 때, 

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

 

다음과 같이 누적합 배열(sumArr)을 따로 생성해 줍니다.

sumArr[i][j]를 채우는 방법은 arr[i][j] + sumArr[i][j - 1] + sumArr[i - 1][j] - sumArr[i - 1][j - 1] 입니다.

1	3  => 1 + 2	6  => 1 + 2 + 3	10  => 1 + 2 + 3 + 4
3  => 1 + 2	8  => 3 + 3 + 3 - 1	15  => 4 + 6 + 8 - 3	24
6  => 1 + 2 + 3	15	27	42
10  => 1 + 2 + 3 + 4	24	42	64

 

마지막으로 (x1, y1, x2, y2)가 주어졌을 때 구간 합을 구하는 방법은 sumArr[x2][y2] - sumArr[x2][y1 - 1] - sumArr[x1 - 1][y2] + sumArr[x1 - 1][y1 - 1] 입니다.

 

sumArr에서 IndexOutOfBoundsException을 피하기 위해서 0으로 채워진 0행과 0열을 추가하였습니다.