15724번. 주지수

누적합

: 누적합이어서, 열마다 처리하는 방식으로 했는데, 시간초과 발생함.

• 아예 행과 열 누적합 처리하는 방식으로 진행 해야 함.

• 열마다 처리할 경우
  

정답 코드

• 3,3 ~ 4,4 일 경우, 어떻게 처리할 것인지를 작성해야 함.
  

#include <iostream>
#include <vector>
using namespace std;
#include <algorithm>
#include <queue>
#include <string>

//15724 주지수 
// 17: 32 ~ 18:14

int main()
{
	// 행마다 누적합을 하고 

	// 열 처리할때는 해당 열의 누적된 합을 가지고 와서 처리하자. ?? 

	// 누적합이니까 
	// dp[][1] 부터 시작하자.
	// d[행은 고정][i] = d[][i - 1] + v[][i] 

	// 만약 1열 2행 부터 4행까지라면 : dp[1][4] - dp[1][2 1]

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	vector<vector<int>>v(n + 1, vector<int>(m + 1));
	vector<vector<int>>psum(n + 1, vector<int>(m + 1, 0));

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			cin >> v[i][j];
			// 2차원 배열 누적합 설정하기 
			psum[i][j] = psum[i][j - 1] + v[i][j]
				+ psum[i - 1][j] -psum[i - 1][j - 1];
		}
	}

	int k;
	cin >> k;

	for (int i = 0; i < k; ++i)
	{
		int x1, y1, x2, y2;
		cin >> y1 >> x1 >> y2 >> x2;
		// 1 1 3 2 
		cout << psum[y2][x2] - psum[y1 - 1][x2]
			- psum[y2][x1- 1] + psum[y1 - 1][x1 - 1] << '\n';
	}

	// 확인용 
	//for (int i = 1; i <= n; ++i)
	//{
	//	for (int j = 1; j <= m; ++j)
	//	{
	//		cout << psum[i][j] << " ";
	//	}
	//	cout << endl;
	//}

}
// 37 66 -> 103
// 177 - 52 - 31
// 177 - 83 : 94 + 중복되는 거 처리 이때는 [0][0]

// 40 16 11 23 -> 56 34 -> 90 
// 293 - 110 - 148 + 55
// 293 - 258 + 55
// 38 + 55 
//y1 x1 y2 x2
// 3 3 ~ 4 4

1. psum 설정을 하자.

• psum[2][2] 는 v[2][2] + psum[1][2] + psum[2][1] - psum[2 -1][2 -1](마지막 원소는 중복 처리)

• 코드로 나타내면

  

2. 계산하기

: 여기를 구하는 것은 어떻게 할것이냐?

• 그림과 같이 진행을 하면 됨.
  : 코드 작성에 실수 할 수 있으므로. 주석으로 작성하면서 처리하자.
  

잘못된 코드

#include <iostream>
#include <vector>
using namespace std;
#include <algorithm>
#include <queue>
#include <string>

//15724 주지수 
// 17: 32 ~ 18:14

int main()
{
	// 행마다 누적합을 하고 

	// 열 처리할때는 해당 열의 누적된 합을 가지고 와서 처리하자. ?? 

	// 누적합이니까 
	// dp[][1] 부터 시작하자.
	// d[행은 고정][i] = d[][i - 1] + v[][i] 

	// 만약 1열 2행 부터 4행까지라면 : dp[1][4] - dp[1][2 1]

	int n, m;
	cin >> n >> m;

	vector<vector<int>>v(n + 1, vector<int>(m + 1));
	vector<vector<int>>psum(n + 1, vector<int>(m + 1, 0));

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			cin >> v[i][j];
			psum[i][j] = psum[i][j - 1] + v[i][j];
		}
	}

	int k;
	cin >> k;

	for (int i = 0; i < k; ++i)
	{
		int x1, y1, x2, y2;
		cin >> y1 >> x1 >> y2 >> x2;

		// 1 1 3 2
		// x : 1 ~ 2
		// y : 1 ~ 3
		int sum = 0;
		for (int a = y1; a <= y2; ++a)
		{
			//cout << psum[a][x2] - psum[a][x1 - 1] << endl;
			sum += psum[a][x2] - psum[a][x1 -1];
		}
		cout << sum << endl;
	}
	
	//for (int i = 1; i <= n; ++i)
	//{
	//	for (int j = 1; j <= m; ++j)
	//	{
	//		cout << psum[i][j] << " ";
	//	}
	//	cout << endl;
	//}

}