[백준 BOJ][DP] 2167 2차원 배열의 합

2167_2차원 배열의 합

링크

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

 

풀이

 

DP[i][j] (1 <= i, j <= 300)을 구간 [1, 1] ~ [i, j]의 합이라고 정의합니다.

 

 

DP[1][4]입니다.

 

 

DP[3][2]입니다.

 

그렇다면 DP[i][j]를 구하는 방법을 알아보겠습니다.

 

DP[i][j] = DP[i-1][j] + DP[i][j-1] – DP[i-1][j-1] + arr[i][j]

두 개의 구간합에서 겹치는 부분을 빼주고 자신을 더하는 방식으로 구할 수 있습니다.

 

 

그렇다면 이 구간합을 가지고 어떻게 답을 구할 수 있을까요?

 

예를 들어 (3, 3) ~ (4, 5)의 구간합을 구한다고 생각해봅시다.

 

 

(1, 1) ~ (4, 5)의 합에서 좌측과 상단을 쳐내고 두 번 겹친 DP[2][2]를 다시 더해줌으로써 구할 수 있습니다.

일반화하면 (j, i) ~ (y, x)의 합을 구하고 싶다면,

DP[y][x] ((1, 1) ~ (y, x)의 합에서) – DP[y][i - 1] (좌측을 쳐내고) - DP[j - 1][x] (우측을 쳐내고) + DP[j-1][i-1] (두 번 쳐낸 곳을 더해 줌)이라는 식으로 답을 구할 수 있습니다.

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

//2167_2차원 배열의 합 #include <cstdio> #include <algorithm> using namespace std;   int DP[301][301], n, m, k, i, j, x, y, tmp;   int main() {     scanf("%d %d", &n, &m);       for (int i = 1; i <= n; ++i) {         for (int j = 1; j <= m; ++j) {             scanf("%d", &tmp);             DP[i][j] = DP[i - 1][j] + DP[i][j - 1] - DP[i - 1][j - 1] + tmp;         }     }       scanf("%d", &k);       while (k--) {         scanf("%d %d %d %d", &j, &i, &y, &x);         printf("%d\n", DP[y][x] - DP[y][i - 1] - DP[j - 1][x] + DP[j-1][i-1]);     }          return 0; } Colored by Color Scripter

cs