[Algorithm] 50. 영지(territory) 선택

 

인트로

피보나치 수열로 동적 프로그래밍을 이해했다면 그다음 단계로 풀어볼 적당한 문제인 것 같다.

영지(territory)선택

 

문제

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

전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요.

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

※ 입력 설명
첫 줄에 H(세로길이)와 W(가로길이)가 입력된다. (1<=H, W<=700) 그다음 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

코드 설명

DP Table의 (N, M)에 저장될 데이터는 Map의 시작점(1, 1)부터 (N, M)까지 저장된 수의 합이다.

아래의 표를 예로 들면, DP Table의 (1, 2)는 Map의 (1, 1)부터 (1, 2)까지 저장된 수의 합(3 + 5)이다.

 

하나만 더 DP Table을 채워보면 DP Table의 (2, 2)는 Map의 (1 ,1), (1, 2), (2, 1) (2, 2)의 합 11이다.

 

그렇다면 본 문제를 동적 프로그래밍으로 해결할 수 있고 가능한 이유는 다음과 같다.

DP Table의 값을 구하는 과정을 "반복적인 부분 문제"로 쪼개서 풀 수 있고 "부분 문제"도 "큰 문제"의 연산과 동일하다.

 

?는 붉은 네모칸 숫자들의 합이다. 19는 푸른 네모칸 숫자들의 합이다. 18은 녹색 네모칸 숫자들의 합이다.

우리가 알 수 있는 건, ?을 구하는 연산은 푸른 네모칸 + 녹색 네모칸 -노란색 영역 + Map(4, 3)이라는 것이다.

숫자로 표현하면 ? = 19 + 18 - 13 + 5이 된다.

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

int main()
{
	int h1, w1, h2, w2, sum, res = 1;

	cin >> h1 >> w1;

	vector<vector<int>> matrix(h1 + 1, vector<int>(w1 + 1));
	vector<vector<int>> dp(h1 + 1, vector<int>(w1 + 1, 0));

	for (int y = 1; y <= h1; y++)
	{
		for (int x = 1; x <= w1; x++)
		{
			cin >> matrix[y][x];
			dp[y][x] = matrix[y][x] + dp[y - 1][x] + dp[y][x - 1] - dp[y - 1][x - 1];
		}
	}

	cin >> h2 >> w2;

	for (int y = h2; y <= h1; y++)
	{
		for (int x = w2; x <= w1; x++)
		{
			sum = dp[y][x] - dp[y - h2][x] - dp[y][x - w2] + dp[y - h2][x - w2];

			res = sum > res ? sum : res;
		}
	}

	cout << res;
}