2167번: 2차원 배열의 합

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

2167번: 2차원 배열의 합

 

 

다이나믹 프로그래밍 문제인데, 점화식의 정의를 어떻게 하는가가 중요한 문제이다. 점화식은 어떤 n에 대해서도 해당하기 때문에, 1부터 원하는 n까지 구할 수 있다.

 

 

 

---

 

 

 

dp[301][301]을 선언하고, dp[i][j]는 0,0에서 i,j라고 하자.

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j]

 

 

 

 

위의 식은 어떤 i, j에 대해서도 만족한다. 즉, 점화식이 되는 것이다.

 

 

 

 

위의 식을 이용하면, 임의의 점 x, y부터 i, j까지 직사각형을 이루는 배열 원소들의 합을 구할 수 있다.

 

 

 

 

배열 원소들의 합 = dp[i][j] - dp[x - 1][j] - dp[i][y - 1] + dp[x - 1][y - 1]

 

 

 

---

 

해설코드(C++).

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N, M, K;
int main(void) {
    cin >> N >> M;
    int dp[301][301] = { 0 };
    int arr[301][301] = { 0 };
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> arr[i][j];
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
        }
    }
 
    cin >> K;
    for (int i = 1; i <= K; i++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << dp[r2][c2] - dp[r1 - 1][c2] - dp[r2][c1 - 1] + dp[r1 - 1][c1 - 1] << endl;
    }
    
    return 0;
}