백준 11660번 : 구간 합 구하기 5

문제 링크 :  https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

 문제설명 

 

1. 배열의 크기 N 과 구간의 갯수 M이 주어짐

2. 예를들어 N이 4 구간이 (2 , 2) , (3 , 4)  가주어지면

색칠된 구간의 합을 구하면 된다 .

 

 알고리즘 

 

1.구간합 배열을 2차로 만든다 .

2.  구간이 (2 , 2) , (3 , 4)  가주어지면 

3. 먼저 (1,1) , (3,4) 의 구간합을 구함

   -> 그리고 (1,1) , (1,4) 구간합과 , (1,1) ,(3,1) 구간합을 빼준다 그리고 (1,1)을  더해준다.

점화식 :  result = arr[3][4] -arr[3][1]-arr[1][4]+arr[1][1] 

 

 코드 

 

#include<iostream>
 
using namespace std;
int main() {
    int N, M;
 
    scanf("%d%d", &N, &M);
 
    int sum[1025][1025];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int a;
            scanf("%d", &a);
            sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + a;
        }
    }
    for (int i = 0; i < M; i++) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        printf("%d\n", sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1]);
    }
}