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

문제 출처 : https://www.acmicpc.net/problem/2167

문제 요약

• 정보가 담긴 2차원 배열이 주어진다.
• 2차원 배열 내에 주어진 구간의 합을 구하는 문제이다.

문제 풀이

이 문제는 동적 계획법을 사용하여 부분(구간)합을 구하는 문제이다. 

여기서 부분합이란 ??

배열 정보

4

5

1

2

3

4

부분합 배열

4

9

10

12

15

19

이와 같이 자신의 위치를 포함하여 이전의 값들의 합(누적합)을 배열에 저장해두는 것이다. 

이 원리를 확장하여 2차원 배열에 적용을 한 것이 이 문제의 핵심이다.

(0, 0)
	(a, b)
				(n-1,m-1)

이와 같은 2차원 배열의 정보를 Dp(i, j) : (0,0) 부터 (i, j) 까지의 합을 저장해두자. 

하지만 좌측상단의 시작이 (0,0) 아니라면 ?? 

만약, (a, b)에서 (n-1, m-1)까지의 부분합을 구해야한다고 하면 (문제의 요구) 우리는 집합의 개념을 가져올 수 있다.

즉, 구간합(a,b, n-1, m-1) : dp(n-1, m-1) - dp(a-1, m-1) - dp(n-1, b-1) + dp(a-1, b-1) 과 같이 표현할 수 있다.

이처럼 파란색 구간을 구하기 위해 빨간색 2구간을 빼준 뒤, 초록 구간을 한 번 더 해준다. 이유는

초록구간이 두 번 빼졌기 때문이다. 합집합의 공식을 생각하면 이해하기 쉽다. 

#include <iostream>

#include <vector>

#define MAX 300

using namespace std;

int dp[MAX + 1][MAX + 1];

int n, m, k;

int main() {

cin >> n >> m;

vector< vector<int> > a(n, vector<int>(m));

//입력

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

cin >> a[i][j];

}

}

//부분합결과 저장하기

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

//(0, 0)

if (i == 0 && j == 0) {

dp[i][j] = a[i][j];

}

//(0, ?)

else if (i == 0 && j != 0) {

dp[i][j] = a[i][j] + dp[i][j - 1];

}

//(?, 0)

else if (i != 0 && j == 0) {

dp[i][j] = a[i][j] + dp[i - 1][j];

}

//(?, ?)

else {

dp[i][j] = a[i][j] + dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];

}

}

}

cin >> k;

for (int tc = 1; tc <= k; tc++) {

int a, b, c, d;

int ret(0);

// (0, 0) 부터 시작하기 위해서 인덱스를 -1 씩 하였다.

cin >> a >> b >> c >> d;

a--; b--; c--; d--;

if (a != 0 && b != 0)

ret = dp[c][d] - dp[c][b - 1] - dp[a - 1][d] + dp[a - 1][b - 1];

else if (a == 0 && b != 0)

ret = dp[c][d] - dp[c][b - 1];

else if (a != 0 && b == 0)

ret = dp[c][d] - dp[a - 1][d];

else

ret = dp[c][d];

cout << ret << endl;

}

return 0;

}