[BOJ] 11660번 | 구간 합 구하기 5 (C++)

🔗문제 보러가기

11660번: 구간 합 구하기 5

 

🧑‍💻풀이 과정

1. 초기값으로, 1행과 1열 각각의 배열 원소에 누적합을 저장합니다.
2. 2행 2열 ~ N행 N열까지 다음 과정을 반복합니다.
   •  \( N \times N \) 배열을 arr이라고 한다면,
   • arr[row][col] += arr[row - 1][col] + arr[row][col - 1] - arr[row - 1][col - 1]
     • arr[row - 1][col]에는 (row - 1 ) * col 사각형 크기만큼의 누적합이 저장되어 있습니다.
     • arr[row][col - 1]에는 row * (col - 1) 사각형 크기만큼의 누적합이 저장되어 있습니다.
     • 즉, arr[row - 1][col] + arr[row][col - 1]을 하게 되면, arr[row - 1][col - 1]부분이 겹치게 됩니다.
     • 따라서, arr[row - 1][col - 1]을 빼줘야 row * col 사각형의 누적합이 저장되게 됩니다.
     • 그림으로 표현하여 보는 것이 더 이해가 빠를 겁니다.

 

3. (x1, y1)부터 (x2, y2)까지의 사각형 크기 합계는 다음과 같이 구할 수 있습니다.

• (x1, y1)부터 (x2, y2)의 합계 = arr[x2][y2] - arr[x2][y1 - 1] - arr[x1 - 1][y2] + arr[x1 - 1][y1 - 1]

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#define FAST_IO cout.tie(NULL); cin.tie(NULL); ios::sync_with_stdio(false);
using namespace std;

int main()
{
	FAST_IO;

	int N, M;
	cin >> N >> M;

	vector<vector<int>> field(N + 1, vector<int>(N + 1));
	for (int row = 1; row <= N; row++)
	{
		for (int col = 1; col <= N; col++)
		{
			// 1. 0행 0열 값은 그냥 저장하기
			if (row == 1 and col == 1)
			{
				cin >> field[row][col];
				continue;
			}

			int data;
			cin >> data;

			// 2. 0번째 행은 col - 1번째 값에다 새로운 데이터를 더해 누적하여 저장하기
			if (row == 1 and col > 1)
			{
				field[row][col] = field[row][col - 1] + data;
				continue;
			}

			// 3. 0번째 열은 row - 1번째 값에다 새로운 데이터를 더해 누적하여 저장하기
			if (col == 1 and row > 1)
			{
				field[row][col] = field[row - 1][col] + data;
				continue;
			}

			// 4. field[row][col] = [row - 1][col] + [row][col - 1] - [row - 1][col - 1] + data
			field[row][col] = field[row - 1][col] + field[row][col - 1] - field[row - 1][col - 1] + data;
		}
	}


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

		// [x2, y2] 면적 - ([x1 - 1, y2] 까지의 면적) - ([x2, y1 - 1] 까지의 열 면적) + (앞에서 두 번 빼서 겹치는 부분)
		int answer = field[x2][y2] - field[x1 - 1][y2] - field[x2][y1 - 1] + field[x1 - 1][y1 - 1];
		cout << answer << "\n";
	}


	return 0;
}