백준 2167번 - 2차원 배열의 합

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

처음에 이 문제를 풀 때 단순 반복문으로 문제를 풀었다.
물론 정답인데 시간이 약 400ms가 걸리면서 통과하는 걸 보고...DP로 어떻게 접근할지 생각해봤다.


i부터 x까지, j부터 y까지 2중 반복문만 돌면 되는데 문제는 돌려야 하는 k가 10000개까지 있다보니깐
k까지 3중 반복문을 돌게 되면 생각보다 시간이 오래 걸리게 된다.

그렇다고 i,j,x,y를 모두 배열로 담아서 4차원 배열로 담기에는 런타임에러가 날 수도 있다.
즉, 2차원 배열로 접근을 해야 한다.


점화식은 다음과 같다.

dp[y][x] = (0,0)에서 (y, x)까지의 합

 

 

그렇다면 y1, x1에서 y2, x2까지의 합도 구할 수 있게 된다.

dp[y2][x2]=dp[y2][x1-1]-dp[y1-1][x2]+dp[y1][x1]

 

 

이게 무슨 말인지 처음 보면 헷갈릴 수 있는데 그림으로 직접 그려봤다.

 

 

 

 

 

 

위의 그림은 (0,0)에서 (y2, x2)까지의 합을 나타낸 것으로 보기 쉽게 sum으로 표현했다.

 

 

 

 

 

 

 

 

위의 그림은 (0,0)에서 (y5, x4)까지의 합을 나타낸 부분이다. 

편의상 5번째 y좌표와 4번째 x좌표를 y5와 x4로 나타냈다.

 

 

 

 

 

이제 (y2, x2)에서 (y5, x4)까지의 합을 위의 2개를 이용해서 구해보면 다음과 같다.

 

 

 

 

우리가 구해야 할 부분은 빨간색으로 색칠 된 영역이다.

포인트는 dp[y5][x4]에서 dp[y2][x2]를 빼주는 것이 아니라
y2에서 1을 빼준 y1과 기존의 x 좌표인 x4를
x2에서 1을 빼준 x1과 기존의 y 좌표인 y5를
빼줘야 한다.

그리고 y1과 x1까지의 합이 두 번 빼줬기 때문에 다시 y1과 x1까지의 합을 더해줘야 한다.

#include <iostream>
using namespace std;
 
int main(){
    
    int N,M,K;
    cin>>N>>M;
    
    int value=0;
    int dp[301][301]={0}; //(0,0)에서 (n,m)까지의 합
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++){
            scanf("%d",&value);
            dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+value;
        }
    
    cin>>K;
    int sum=0;
    int x1,x2,y1,y2;
    for(int testCase=0;testCase<K;testCase++){
        scanf("%d %d %d %d",&y1,&x1,&y2,&x2);
        
        sum=dp[y2][x2]-dp[y2][x1-1]-dp[y1-1][x2]+dp[y1-1][x1-1];
        printf("%d\n",sum);
    }
    
    return 0;
}