[C++] 영지(territory) 선택 🔥

📄문제

세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다. 전체 땅은 사각형으로 표시된다. 그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(세로의 길이와 가로의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것이다.

전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨져 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요. 다음과 같은 땅의 정보가 주어지고, 현수가 하사받을 크기가, 가로 2, 세로 3의 크기이면 가장 많은 오렌지 나무가 있는 영지는 총 오렌지 나무의 개수가 16인 3행 4열부터 시작하는 구역이다.

 

⬇️ 입력

첫 줄에 H(세로길이)와 W(가로길이)가 입력된다. (5<=H, W<=50)

그 다음 H줄에 걸쳐 각 사각형 지역에 오렌지의 나무 개수(1~9개) 정보가 주어진다.

그 다음 영지의 크기인 세로길이(1~H)와 가로길이(1~W)가 차례로 입력된다.

6 7 3 5 1 3 1 3 2 1 2 1 3 1 1 2 1 3 1 5 1 3 4 5 1 1 3 1 3 2 3 1 1 3 1 1 2 1 3 1 3 1 2 2 2 3

 

⬆️ 출력

첫 줄에 현수가 얻을 수 있는 오렌지 나무의 최대 개수를 출력한다.

16

 

📝 풀이

#include <iostream>

#define rep(N) for(int i = 0; i < N; ++i)

int main()
{
	int zoneW, zoneH, areaW, areaH;
	scanf_s("%d %d", &zoneH, &zoneW); // 총 영역의 세로, 가로

	int** arr = new int* [zoneH];
	rep(zoneH)
		arr[i] = new int[zoneW];

	for (int i = 0; i < zoneH; ++i)
		for (int j = 0; j < zoneW; ++j)
			scanf_s("%d", &arr[i][j]);

	scanf_s("%d %d", &areaH, &areaW); // 하사받을 영역의 세로, 가로

	int max = INT_MIN;

	for (int i = 0; i < zoneH - areaH + 1; ++i)
		for (int j = 0; j < zoneW - areaW + 1; ++j)
		{
			int sum = 0;

			for (int k = i; k < i + areaH; ++k)
				for (int l = j; l < j + areaW; ++l)
					sum += arr[k][l];

			max = max < sum ? sum : max;
		}

	printf("%d", max);
}

• i, j로부터 areaH, areaW만큼 확장된 넓이에 대해 4중 for문을 이용하여 계산합니다.
• 전체 영역의 크기가 넓지 않기때문에 4중 for문을 사용하였지만, 범위가 넓어질수록 속도가 급격히 느려지기때문에 다른 방법을 사용해야합니다.

 

#include <iostream>

#define rep(N) for(int i = 0; i < N; ++i)

int main()
{
	int zoneW, zoneH, areaW, areaH;
	scanf_s("%d %d", &zoneH, &zoneW); // 총 영역의 세로, 가로

	int** arr = new int* [zoneH];
	int** memory = new int* [zoneH]; // 계산했던 값들을 저장할 공간
	rep(zoneH)
	{
		arr[i] = new int[zoneW];
		memory[i] = new int[zoneW];
	}

	for (int i = 0; i < zoneH; ++i)
		for (int j = 0; j < zoneW; ++j)
			scanf_s("%d", &arr[i][j]);

	scanf_s("%d %d", &areaH, &areaW); // 하사받을 영역의 세로, 가로

	int max = INT_MIN;

	for (int i = 0; i < zoneH - areaH + 1; ++i)
		for (int j = 0; j < zoneW - areaW + 1; ++j)
		{
			int sum = 0;

			if (j == 0)
			{
				for (int k = i; k < i + areaH; ++k)
					for (int l = j; l < j + areaW; ++l)
						sum += arr[k][l];
			}
			else
			{
				// 저장되어 있는 값을 가져오기
				sum = memory[i][j - 1];

				for (int k = i; k < i + areaH; ++k)
				{
					sum -= arr[k][j - 1];
					sum += arr[k][j + areaW - 1];
				}
			}

			memory[i][j] = sum; // 영역의 합을 저장
			max = max < sum ? sum : max;
		}

	printf("%d", max);
}

• 각 영역을 계산할 때 sum을 memory라는 배열에 저장합니다.
• 다음 계산을 할 때, memory가 있다면, 해당 값을 가지고오고, 덧셈과 뺄셈을 통해 계산을 최소화하여 개선하였습니다.
• 하지만 이 방식도 최대 4중 for문이기때문에, 더욱 효율적인 방법을 찾아야합니다.

 

#include <iostream>

#define rep(N) for(int i = 0; i < N; ++i)

int main()
{
	int zoneW, zoneH, areaW, areaH;
	scanf_s("%d %d", &zoneH, &zoneW); // 총 영역의 세로, 가로

	int** arr = new int* [zoneH];
	int** memory = new int* [zoneH]; // 계산했던 값들을 저장할 공간
	rep(zoneH)
	{
		arr[i] = new int[zoneW];
		memory[i] = new int[zoneW];
	}

	for (int i = 0; i < zoneH; ++i)
		for (int j = 0; j < zoneW; ++j)
		{
			scanf_s("%d", &arr[i][j]);

			if (i == 0 && j == 0)
				memory[i][j] = arr[i][j];
			else if (i == 0)
				memory[i][j] = memory[i][j - 1] + arr[i][j];
			else if (j == 0)
				memory[i][j] = memory[i - 1][j] + arr[i][j];
			else
				memory[i][j] = memory[i - 1][j] + memory[i][j - 1] - memory[i - 1][j - 1] + arr[i][j];
		}

	scanf_s("%d %d", &areaH, &areaW); // 하사받을 영역의 세로, 가로

	int max = INT_MIN;
	for (int i = areaH - 1; i < zoneH; ++i)
	{
		for (int j = areaW - 1; j < zoneW; ++j)
		{
			int sum = 0;

			if (i == areaH - 1 && j == areaW - 1)
			{
				sum = memory[i][j];
			}
			else if (i == areaH - 1)
			{
				sum = memory[i][j] - memory[i][j - areaW];
			}
			else if (j == areaW - 1)
			{
				sum = memory[i][j] - memory[i - areaH][j];
			}
			else
			{
				sum = memory[i][j] - memory[i - areaH][j] - memory[i][j - areaW] + memory[i - areaH][j - areaW];
			}

			max = sum > max ? sum : max;
		}
	}

	printf("%d", max);
}

• 마지막 방법은 해당 영역에 오렌지나무의 개수를 입력할 때, 처음부터 해당 위치까지의 직사각형 영역에 대한 합을 모두 더한 누적된 값을 memory 배열에 입력합니다.
• 모든 영역이 memory에 저장되면, 조건에 따라 중복되는 영역의 합을 빼어 O(n^2)의 시간 복잡도로 해결할 수 있습니다.