Problem B : const구간의 합 구하기(2D)

Problem B : const구간의 합 구하기(2D)

 

제한시간: 2000 ms    메모리제한: 512 MB

 

 

N * N크기의 2차원 배열에 수들이 입력되어 있다.

 

이 배열의 임의의 구간에 있는 수들의 합을 

물어보는 M개의 쿼리에 답하는 프로그램을 작성하시오.

 

쿼리에 답하는 중간에 배열의 어떤 원소도 값이 변경되지 않는다.​ 

첫 행에 행과 열의 크기 N이 입력된다. ( 1 <= N <= 1,000) 다음 N개의 행에 걸쳐 N개의 수 Ai가 공백을 구분하여 입력된다. ( -1,000,000 <= Ai <= 1,000,000) 다음 행에 쿼리의 수 M이 입력된다. ( 1 <= M <= 1,000,000) 이어서 M개의 행에 쿼리의 정보 sri, sci, eri, eci가 공백으로 구분되어 입력된다. ( 1<= sri <= eri<= N, 1<= sci <= eci<= N)

각 쿼리에 대한 결과를 행으로 구분하여 출력한다.

 

5

1 2 3 4 5

6 7 8 9 0

-1 2 1 1 1

5 2 3 1 4

1 0 1 0 1

3

2 1 2 1

3 3 5 5

1 1 5 5

 

6

13

67

 

#include <stdio.h>

#define MAX 6 // 1010
int N, M;
long long A[MAX][MAX];

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%lld", &A[i][j]);
			A[i][j] += A[i][j - 1] + A[i - 1][j] - A[i - 1][j - 1]; // 누적합을 계산함 N^2 입력과 동시
		}
	}
	scanf("%d", &M);
	int sy, sx, ey, ex;
	while (M--) {
		scanf("%d %d %d %d", &sy, &sx, &ey, &ex);
		sy--, sx--;
		printf("%lld\n", A[ey][ex] + A[sy][sx] - A[sy][ex] - A[ey][sx]); // 2D 누적합 이렇게 계산
	}
	return 0;
}