(2167)(DP) 백준 2차원 배열의 합

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

풀이

---

문제 설명이 구체적으로 되어있지 않아서 헤맸다.

ex)

arr[1][1]    arr[1][2]    arr[1][3]    arr[1][4]

arr[2][1]    arr[2][2]    arr[2][3]    arr[2][4]

arr[3][1]    arr[3][2]    arr[3][3]    arr[3][4]        와 같은 2차원 배열이 존재한다고 하고

문제를 이해하기로는 

i,j,x,y에 2,2,3,3을 주면

arr[1][1]    arr[1][2]    arr[1][3]    arr[1][4]

arr[2][1]    arr[2][2]    arr[2][3]    arr[2][4]

arr[3][1]    arr[3][2]    arr[3][3]    arr[3][4]    <-- 빨간 부분의 배열의 총 합을 구하는 거라고 생각했지만 X

arr[1][1]    arr[1][2]    arr[1][3]    arr[1][4]

arr[2][1]    arr[2][2]    arr[2][3]    arr[2][4]

arr[3][1]    arr[3][2]    arr[3][3]    arr[3][4]   <-- 이와 같이 사각형의 형태의 배열의 총 합을 구하는 문제였다.

그래서 나는 dp[i][j]를 이용해서 arr[1][1] 부터 arr[i][j]까지  총합을 구했다.

for (int i = 1; i <= N; i++) {

dp[i][1] = arr[i][1] + dp[i - 1][M];

for (int j = 2; j <= M; j++) {

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

}

}

그후에  x좌표의 값을 기준으로 for문을 이용해 이전에 구해 놓았던 dp값을 활용해서 한줄씩 부분 배열의 합을 구하기로 한다.

for (int i = 1; i <= T; i++) {

scanf("%d %d %d %d", &a, &b, &x, &y);

for (a; a <= x; a++) {

r += dp[a][y] - dp[a][b]+ arr[a][b];

}

printf("%d\n", r);

r = 0;

}

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int main() {
    int arr[301][301] = { 0 };
    int dp[301][301] = { 0 };
    int N, M, T;
    int a, b, x, y;
    int r = 0;
 
    scanf("%d %d", &N, &M);
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 1; i <= N; i++) {
        dp[i][1] = arr[i][1] + dp[i - 1][M];
        for (int j = 2; j <= M; j++) {
            dp[i][j] += dp[i][j-1] + arr[i][j];
        }
        
    }
 
    scanf("%d", &T);
 
    for (int i = 1; i <= T; i++) {
        scanf("%d %d %d %d", &a, &b, &x, &y);
        for (a; a <= x; a++) {
            r += dp[a][y] - dp[a][b]+ arr[a][b];
        }
        printf("%d\n", r);
        r = 0;
    }
 
    return 0;
}