백준 2167 2차원 배열의 합

<DP를 적용하지 않고 for문을 돌려 배열의 합을 구한 경우>

#include <cstdio>
using namespace std;
 
int arr[301][301];
int n, m;
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    int k;
    scanf("%d", &k);
    while (k--) {
        int a, b, x, y;
        scanf("%d %d %d %d", &a, &b, &x, &y);
        int sum = 0;
        for (int i = a; i <= x; i++) {
            for (int j = b; j <= y; j++) {
                sum += arr[i][j];
            }
        }
        printf("%d\n", sum);
    }
    return 0;
}
 

이렇게 답안을 제출해도 정답처리가 된다.

하지만 배열이 커지고 구해야 할 부분합의 갯수가 많아질 경우 시간초과가 날 것이다.

그러므로 이 문제를 DP를 이용하여 풀어보면 다음과 같다.

<DP를 적용하여 문제를 푼 경우>

#include <cstdio>
using namespace std;
 
int arr[301][301];
int d[301][301];
int n, m;
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &arr[i][j]);
            d[i][j] = arr[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
        }
    }
    int k;
    scanf("%d", &k);
    while (k--) {
        int a, b, x, y;
        scanf("%d %d %d %d", &a, &b, &x, &y);
        printf("%d\n", d[x][y] - d[a - 1][y] - d[x][b - 1] + d[a - 1][b - 1]);
    }
    return 0;
}

걸린 시간을 비교해보면 

DP로 풀었을 때 걸린 시간이 20분의 1로 줄었다는 것을 확인할 수 있다. (하지만 메모리를 더 씀..)

(중간에 시간초과는 코딩실수....)