🙇‍♀️영지 선택 (large)

세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다.

전체 땅은 사각형으로 표시된다.

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

전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨져 있다.

현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 한다.

현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요.

다음과 같은 땅의 정보가 주어지고, 현수가 하사받을 크기가, 가로 2, 세로 3의 크기이면 가장 많은 오렌지 나무가 있는 영지는 총 오렌지 나무의 개수가 16인 3행 4열부터 시작하는 구역이다.

영지

▣ 입력설명
첫 줄에 H(세로길이)와 W(가로길이)가 입력된다.  

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

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

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

▣ 입력예제 1 
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

▣ 출력예제 1
16

🚀풀이

DP를 이용한 풀이이다.

cache에는 그 위치까지의 누적합을 넣는다.
cache를 채워주는 방법은 점화식을 만들어서 도출할 수 있는데,
cache[y][x] = board[y][x] + cache[y - 1][x] + cache[y][x - 1] - cache[y - 1][x - 1]
와 같다.

영지를 cache를 이용해서 계산하면,
영지 계산
분홍색 영역을 구해야하므로 초록색 부분을 제외해야한다.
초록색 부분 역시 cache를 통해서 구할 수 있다.
해당 위치의 영지는 아래와 같이 계산된다.
temp = cache[y][x] - cache[y - areaH][x] - cache[y][x - areaW] + cache[y - areaH][x - areaW]

위를 이용해서 풀이를 적으면 아래와 같다.

int board[701][701], cache[701][701];
int h, w, areaH, areaW, temp, res = 0;
void solve()
{
	cin >> h >> w;
	for (int y = 1; y <= h; ++y)
	{
		for (int x = 1; x <= w; ++x)
		{
			cin >> board[y][x];
			cache[y][x] = board[y][x] + cache[y - 1][x] + cache[y][x - 1] - cache[y - 1][x - 1]; // 캐시 채워주기.
		}
	}

	cin >> areaH >> areaW;

	for (int y = areaH; y <= h; ++y)
	{
		for (int x = areaW; x <= w; ++x)
		{
            // 영지 계산
			temp = cache[y][x] - cache[y - areaH][x] - cache[y][x - areaW] + cache[y - areaH][x - areaW];
			if (temp > res)
				res = temp;
		}
	}

	cout << res << '\n';
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include<iostream>

using namespace std;

int board[701][701], cache[701][701];
int h, w, areaH, areaW, temp, res = 0;
void solve()
{
	cin >> h >> w;
	for (int y = 1; y <= h; ++y)
	{
		for (int x = 1; x <= w; ++x)
		{
			cin >> board[y][x];
			cache[y][x] = board[y][x] + cache[y - 1][x] + cache[y][x - 1] - cache[y - 1][x - 1];
		}
	}

	cin >> areaH >> areaW;

	for (int y = areaH; y <= h; ++y)
	{
		for (int x = areaW; x <= w; ++x)
		{
			temp = cache[y][x] - cache[y - areaH][x] - cache[y][x - areaW] + cache[y - areaH][x - areaW];
			if (temp > res)
				res = temp;
		}
	}

	cout << res << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고