[BOJ]11660번: 구간 합 구하기 5

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

---

2차원 DP 문제입니다.

 

dp[i][j] : board[i][j] ~ board[N][j] ~ board[i][N] ~ board[N][N]의 합

즉, 쉽게 말해서 board[i][j] 좌표에서 아래쪽과 오른쪽으로 직선을 그었을 때 만들어지는 직사각형 영역의 합을 가지고 있습니다.

 

dp를 이렇게 정의하면 주어진 구간합은 아래와 같이 구할 수 있습니다.

(r1,c1) ~ (r2,c2)의 구간합 = dp[r1][c1] - dp[r2+1][c1] - dp[r1][c2+1] + dp[r2+1][c2+1]

 

이 부분은 그림을 직접 그려보시면 좀 더 쉽게 이해하실 수 있을 겁니다.

 

그래서 O(M)에 해결할 수 있습니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ11660.java