[백준] 11660. 구간 합 구하기5

[문제]

 

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

[풀이]

 

표의 크기 N과 합을 구해야 하는 횟수 M이 입력으로 주어진다.

그 다음으로 표의 값이 주어지고 구간의 시작 좌표, 마지막 좌표가 주어진다.

 

이 구간의 합을 구해서 출력하면 된다.

 

처음에는 이중 for문을 사용해서 시작점인 (x1,y1)부터 구간의 마지막 부분인 (x2,y2) 까지의 합을 구했다.

당연히 시간초과가 나왔고 다른 방법을 찾아봤다.

 

찾아보니 DP를 사용해서 구간 합을 구할 수 있었다. 

 

(1,1)부터 (x,y)까지의 구간 합을 배열 DP[x][y]에 저장한다.

DP[N][N]까지 구하고 M번만큼 반복문 하여 각 구간에 대해 구간 합을 출력하면 된다.

 

[그림 1]

위의 그림에서 우리가 구하고 싶은 구간 합의 영역이 4번 영역이라면

4번 영역의 구간 합은 4 = 3+2-1이 된다.

 

 

[그림 2]

각 영역의 오른쪽 아래 부분이 (그림 2에서 진하게 표시된 부분)

해당 영역의 구간 합이므로 아래와 같이 구할 수 있다.

 

 DP[x2][y2]-DP[x2][y1-1]-DP[x1-1][y2] + DP[x1-1][y1-1]

 

[코드]

 

시간 : 228 ms

#include <iostream>
#define MAX 1025


int map[MAX][MAX]={0,};
long long int DP[MAX][MAX]={0,};

int N,M;


int main(void)
{
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            scanf("%d",&map[i][j]);
            DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + map[i][j];
        }
    }
    
    DP[1][1]=map[1][1];
     
    for(int i=0;i<M;i++)    {
        
        int x1,y1,x2,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        std::cout << DP[x2][y2]-DP[x2][y1-1]-DP[x1-1][y2] + DP[x1-1][y1-1] << "\n";
    }
    
    return 0;
    
}