Boj 11660 c++ 구간 합 구하기 5

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

 

직사각형 상에서 두 구간합과 해당 칸의 조합으로 또 다른 구간합을 구할 수 있다는 기하학적 해석이 중요한 문제. 이는 dp배열의 점화식으로 치환이 가능하다.

 

 

#include<iostream>
#define Max 1025
using namespace std;
int N, M, cnt;
int arr[Max][Max];
int dp[Max][Max];//첫 번째 값 부터 i, j 까지의 직사각형 내의서의 합
void init(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int main(){
    init();
    cin>>N>>M;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin>>arr[i][j];
            dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+arr[i][j];
        }
    } int x1, y1, x2, y2, ans;
    for(int i=0; i<M; i++){
        cin>>x1>>y1>>x2>>y2;
        ans=dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];
        cout<<ans<<"\n";
    }

}