[C++] 백준 11660 구간 합 구하기 5

#include <iostream>
 
int arr[1025][1025] = {};
int DP[1025][1025] = {};
 
int main() 
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
 
	int N = 0;
	int M = 0;
	std::cin >> N >> M;
 
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			std::cin >> arr[i][j];
 
			DP[i][j] = DP[i - 1][j] + DP[i][j - 1] - DP[i - 1][j - 1] + arr[i][j];
		}
	}
 
	for (int i = 0; i < M; ++i)
	{
		int iStartX = 0;
		int iStartY = 0;
		int iEndX = 0;
		int iEndY = 0;
		std::cin >> iStartX >> iStartY >> iEndX >> iEndY;
 
		std::cout << DP[iEndX][iEndY] - DP[iStartX - 1][iEndY] - DP[iEndX][iStartY - 1] + DP[iStartX - 1][iStartY - 1] << "\n";
	}
 
	return 0;
}

DP문제 입니다.

가장 아래쪽까지 본인의 위치를 더해서 저장해놓고

원하는 부분만큼만 잘라서 더하고 빼준다는 생각을 해주시면 됩니다.

예를 들어 4,4 에서 2,2 까지 구하고 싶을 때,

DP[4][4]는 0,0 ~ 4,4 까지 더한 것이고

DP[4][1]는 0,0 ~ 4,1까지 더한 것,

DP[1][4]는 0,0 ~ 1,4까지 더한 것입니다.

DP[1][1]은 0,0 ~ 1,1까지 더했습니다.

DP[4][4] - DP[4][1] - DP[1][4] + DP[1][1]은 

4,4까지 모두 더한 다음, 1,4까지 모두 삭제, 4,1까지 모두 삭제했는데 0,0 ~ 1,1을 두번 삭제 했기에 한번 다시 더해줍니다.

라고 생각하시면 됩니다.