BaekJoon 11660번: 구간 합 구하기 5(C++)

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

풀이법

1) 단순 반복문으로는 시간 초과가 발생하기에 DP를 이용해서 푸는 문제이다.

2) 각 행의 합을 구해두고 이를 활용하는 방식으로 문제를 해결했다.

3) 좌표가 들어오는 경우 점화식을 활용하여, sum 값을 구해 주었다.

	for (int i = 0; i < m; i++)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int sum = 0;
		for (int j = x1; j <= x2; j++)
		{
			sum += arr[j][y2] - arr[j][y1 - 1];
		}

		cout << sum<<"\n";
	}

조건이 y2>=y1이기에, 같은 행에서 나올 수 있는 최대 값인 arr[j][y2]에서, arr[j][y1-1]을 빼주는 방식으로 문제를 해결하였다.

#include<iostream>

using namespace std;
int n,m;
int arr[1025][1025];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int temp;
			cin >> temp;
			arr[i][j] = arr[i][j - 1] + temp;
			
		}
	}
	for (int i = 0; i < m; i++)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int sum = 0;
		for (int j = x1; j <= x2; j++)
		{
			sum += arr[j][y2] - arr[j][y1 - 1];
		}

		cout << sum<<"\n";
	}


}