BOJ 2167번 (2차원 배열의 합)

• 문제
  2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.
  
  
• 입력
  첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).
  
  
• 출력
  K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 2^31-1보다 작거나 같다.

#include<iostream>
#include<vector>
using namespace std;
//int arr[301][301];
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

int main()
{
	int N, M, K, sum = 0; cin >> N >> M;
	int i = 0, j = 0, x = 0, y = 0;
	int** arr = new int* [N];
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[M];
	}

	for (int a = 0; a < N; a++)
	{
		for (int b = 0; b < M; b++)
		{
			int num; cin >> num;

			arr[a][b] = num;
		}
	}
	cin >> K;
	while (K--)
	{
		cin >> i >> j >> x >> y;
		for (int r = i - 1; r < x; r++)
		{
			for (int s = j - 1; s < y; s++)
			{
				sum += arr[r][s];
			}
		}
		cout << sum << '\n';
		sum = 0;
	}
}

   2차원 배열을 전역으로 선언하거나 동적할당 하여 사용하는 방법이 있다.
  단순히 원하는 index까지의 합만 구해주면 된다.

*2차원 배열 동적할당 하는 방법 (heap 영역)

int** arr = new int* [N];
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[M];
	} //N은 행, M은 열

*메모리 해제 방법

for(int i=0; i<N; i++)
 	delete[] arr[i];
delete[] arr; 

시간 복잡도 : O(n^2)

시간 복잡도 : sum을 구하는 과정에서 중첩반복문 + while문으로 인해 c(n^2)인 것 같다.