#include <stdio.h>
#include <vector>
using namespace std;
int main()
{
int h , w, sh, sw, max = 0, temp = 0;
scanf("%d %d", &h, &w);
vector<int> num(w+1, 0);
vector<vector<int>> ter(h+1, num);
vector<vector<int>> ans(h+1, num);
for(int i = 1; i < ter.size(); i++)
{
for(int j = 1; j < num.size(); j++)
scanf("%d", &num[j]);
ter[i] = num;
}
scanf("%d %d", &sh, &sw);
for(int i = 1; i <= h; i++)
{
for(int j = 1; j <= w; j++)
{
ans[i][j] = ans[i][j-1] + ans[i-1][j] - ans[i-1][j-1] + ter[i][j];
}
}
for(int i = sh; i <= h; i++)
{
for(int j = sw; j <= w; j++)
{
temp = ans[i][j] - ans[i-sh][j] - ans[i][j-sw] + ans[i-sh][j-sw];
if(temp > max) max = temp;
}
}
printf("%d", max);
return 0;
}1. 전체 영지 크기를 h,w, 선택 영지의 크기를 sw,sh, 최대 개수를 max, 해당 구간의 개수를 temp 로 선언한다.
2. 다이나믹 프로그래밍(DP) 를 이용하여 푸는 방법이다.
DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.
큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. 그래서 혹자는 DP가 아닌 '기억하며 풀기'라고 부르기도 한다.
DP가 적용되기 위해서는 2가지 조건을 만족해야 한다.
1) Overlapping Subproblems(겹치는 부분 문제)
2) Optimal Substructure(최적 부분 구조)
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 3 | 5 | 1 | 3 | 1 | 3 | 2 |
| 0 | 1 | 2 | 1 | 3 | 1 | 1 | 2 |
| 0 | 1 | 3 | 1 | 5 | 1 | 3 | 4 |
| 0 | 5 | 1 | 1 | 3 | 1 | 3 | 2 |
| 0 | 3 | 1 | 1 | 3 | 1 | 1 | 2 |
| 0 | 1 | 3 | 1 | 3 | 1 | 2 | 2 |
전체 영지에서 나무의 개수를 저장한 vector<int> ter 의 크기는 h+1 * w+1 이다. (0 ~ h, 0)과 (0, 0 ~ w)은 모두 0으로 채워준다. 나무의 개수는 (1, 1) 부터 시작한다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 3 | 5 | 1 | 3 | 1 | 3 | 2 |
| 0 | 1 | 2 | 1 | 3 | 1 | 1 | 2 |
| 0 | 1 | 3 | 1 | 5 | 1 | 3 | 4 |
| 0 | 5 | 1 | 1 | 3 | 1 | 3 | 2 |
| 0 | 3 | 1 | 1 | 3 | 1 | 1 | 2 |
| 0 | 1 | 3 | 1 | 3 | 1 | 2 | 2 |
숫자 3은 (1, 1) 부터 (1, 1) 까지의 합으로 3이다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 3 | 8 | 1 | 3 | 1 | 3 | 2 |
| 0 | 1 | 2 | 1 | 3 | 1 | 1 | 2 |
| 0 | 1 | 3 | 1 | 5 | 1 | 3 | 4 |
| 0 | 5 | 1 | 1 | 3 | 1 | 3 | 2 |
| 0 | 3 | 1 | 1 | 3 | 1 | 1 | 2 |
| 0 | 1 | 3 | 1 | 3 | 1 | 2 | 2 |
숫자 5는 (1, 1) 부터 (1, 2) 까지의 합으로 3 + 5 = 8이다. 이 방식을 반복해보면 아래와 같다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 3 | 8 | 9 | 12 | 13 | 16 | 18 |
| 0 | 4 | 11 | 13 | 19 | 21 | 25 | 29 |
| 0 | 5 | 15 | 18 | 29 | 32 | 39 | 47 |
| 0 | 10 | 21 | 25 | 39 | 43 | 53 | 63 |
| 0 | -- | -- | -- | -- | -- | -- | -- |
| 0 | -- | -- | -- | -- | -- | -- | -- |
해당 문제에서는 파란색 숫자로 되어있는 구간이 나무의 개수가 가장 많은 구간으로 되어있다. 이 구간인지 구별을 어떻게 할까 고민해보면 위와 같은 테이블을 만든 원리와 비슷하다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 3 | 5 | 1 | 3 | 1 | 3 | 2 |
| 0 | 1 | 2 | 1 | 3 | 1 | 1 | 2 |
| 0 | 1 | 3 | 1 | 5 | 1 | 3 | 4 |
| 0 | 5 | 1 | 1 | 3 | 1 | 3 | 2 |
| 0 | 3 | 1 | 1 | 3 | 1 | 1 | 2 |
| 0 | 1 | 3 | 1 | 3 | 1 | 2 | 2 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 3 | 8 | 9 | 12 | 13 | 16 | 18 |
| 0 | 4 | 11 | 13 | 19 | 21 | 25 | 29 |
| 0 | 5 | 15 | 18 | 29 | 32 | 39 | 47 |
| 0 | 10 | 21 | 25 | 39 | 43 | 53 | 63 |
| 0 | -- | -- | -- | -- | -- | -- | -- |
| 0 | -- | -- | -- | -- | -- | -- | -- |
53이라는 숫자는 (1, 1) 부터 (4, 6) 까지 모든 수의 합이다. 그러나 더 간단하게 표현할 수 있다.
43은 (1, 1) 부터 (4, 5) 까지의 합이다. 39는 (1, 1)부터 (3, 6) 까지의 합이다. 두 합의 교집합은 노란색 숫자가 된다.
따라서 43 + 39 - 32 + 3 (실제로 53 자리에 있는 숫자) = 53이 된다. 코드로 표현하면 다음과 같다.
ans[i][j] = ans[i][j-1] + ans[i-1][j] - ans[i-1][j-1] + ter[i][j];그렇다면 해당 구간의 숫자의 합은 어떻게 구할 수 있을까? 방법은 아주 간단하다. 위 방법과 동일하기 때문이다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 3 | 5 | 1 | 3 | 1 | 3 | 2 |
| 0 | 1 | 2 | 1 | 3 | 1 | 1 | 2 |
| 0 | 1 | 3 | 1 | 5 | 1 | 3 | 4 |
| 0 | 5 | 1 | 1 | 3 | 1 | 3 | 2 |
| 0 | 3 | 1 | 1 | 3 | 1 | 1 | 2 |
| 0 | 1 | 3 | 1 | 3 | 1 | 2 | 2 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 3 | 8 | 9 | 12 | 13 | 16 | 18 |
| 0 | 4 | 11 | 13 | 19 | 21 | 25 | 29 |
| 0 | 5 | 15 | 18 | 29 | 32 | 39 | 47 |
| 0 | 10 | 21 | 25 | 39 | 43 | 53 | 63 |
| 0 | -- | -- | -- | -- | -- | -- | -- |
| 0 | -- | -- | -- | -- | -- | -- | -- |
53까지의 전체 구간에서 먼저 초록색 구간인 25까지의 합을 뺀다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 3 | 8 | 9 | 12 | 13 | 16 | 18 |
| 0 | 4 | 11 | 13 | 19 | 21 | 25 | 29 |
| 0 | 5 | 15 | 18 | 29 | 32 | 39 | 47 |
| 0 | 10 | 21 | 25 | 39 | 43 | 53 | 63 |
| 0 | -- | -- | -- | -- | -- | -- | -- |
| 0 | -- | -- | -- | -- | -- | -- | -- |
이후 보라색 구간인 25까지의 합을 뺀다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 3 | 8 | 9 | 12 | 13 | 16 | 18 |
| 0 | 4 | 11 | 13 | 19 | 21 | 25 | 29 |
| 0 | 5 | 15 | 18 | 29 | 32 | 39 | 47 |
| 0 | 10 | 21 | 25 | 39 | 43 | 53 | 63 |
| 0 | -- | -- | -- | -- | -- | -- | -- |
| 0 | -- | -- | -- | -- | -- | -- | -- |
초록색 구간과 보라색 구간의 교집합인 노란색 부분을 두 번 빼주었기 때문에 한 번 더해준다.
53 - 25 - 25 + 13 = 16이 된다.
temp = ans[i][j] - ans[i-sh][j] - ans[i][j-sw] + ans[i-sh][j-sw];이렇게 전체 구간을 돌면서 가장 나무의 개수가 많은 구간을 찾아 그 개수를 출력해주면 된다.
