51. 영지(territory)선택 (large) Dynamic Programming

문제

세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다. 전체 땅은 사각형으로 표 시된다. 그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(세로의 길이와 가 로의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것이다.
전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨져 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하 고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요.
다음과 같은 땅의 정보가 주어지고, 현수가 하사받을 크기가, 가로 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 <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	//freopen("input.txt", "rt", stdin);
	int height, width, i, j, n, m, temp, max=-2147000000;
	scanf("%d %d", &height, &width);
	vector< vector<int>> territory(height+1, vector<int>(width+1));
	vector< vector<int>> dy(height+1, vector<int>(width+1));
	
	for(i=1; i<=height; i++){
		for(j=1; j<=width; j++){
			scanf("%d", &territory[i][j]);
			dy[i][j] = dy[i-1][j] + dy[i][j-1] - dy[i-1][j-1] + territory[i][j];
		}
	}
	scanf("%d %d", &n, &m);
	
	for(i=n; i<=height; i++){
		for(j=m; j<=width; j++){
			temp = dy[i][j] - dy[i-n][j] - dy[i][j-m] + dy[i-n][j-m];
			if(temp > max){
				max = temp;
			}
		}
	}
	printf("%d", max);
	
	return 0;
}

이 강의가 좋은점이 small과 large로 각각 주어지는 입력값이 작고 클때 풀이가 달라지는데 달라질때마다 한번 더 리팩토링하는 느낌이 들어 좋습니다.

굴러만 가는 코드보다는 효율성있는 코드를 짜는것이 프로그래머가 아닐까요? 글로 적는다면 이해하기 꽤 어려울 수 있지만 적어보겠습니다.

territory벡터는 그림과 같이 똑같이 스캔을 합니다. (2, 2)번 인덱스를 예로 들자면 dy벡터의 (1, 2) + (2, 1) - (1, 1)하고 territory벡터의 (2, 2)을 더하는 식으로 하면서 dy벡터를 정의합니다.

(1, 1)을 빼는 이유는 (1, 2) + (2, 1)을 하면 (1, 1)의 요소를 두번 더하는것이기때문에 한번은 빼주는 식입니다.

그렇게 dy벡터를 구했다 치면 기준점을 입력받은 (n, m)인덱스로 두고 (n, m) - (n-n, m) - (n, m-m) + (n-n, m-m)을 하면 (1~n, 1~m)의 오렌지나무의 갯수를 구할수있습니다.