영지 선택(2차원 배열 구간합, DP) / c / 제한시간 : 1초

▣ 문제

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

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>
int map[701][701];
int main() {
	int i, j, k, l;
	int temp = 0;
	int max = -2147000000;
	int h, w, x, y;
	int cnt = 0;

	scanf("%d %d", &h, &w);
	for (i = 1; i <= h; i++) {
		for (j = 1; j <= w; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	scanf("%d %d", &x, &y);

	for (i = 1; i <= h - x + 1; i++) {
		for (j = 1; j <= w - y + 1; j++) {
			temp = 0;
			for (k = 0; k < x; k++) {
				for (l = 0; l < y; l++) {
					temp = temp + map[i + k][j + l];
				}
			}
			if (temp > max) max = temp;
		}
	}
	
	printf("%d\n", max);
	return 0;
}

가장 쉽게 접근하는 방법은 4중 for문 써서 나올수 있는 모든 경우를 직접 계산하는 방법

 

당연히 숫자가 커지면 제한시간 못맞춤

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>
int map[701][701];
int dp[701][701] = { 0 };
int main() {
	int i, j;
	int temp = 0;
	int max = -2147000000;
	int h, w, x, y;
	int cnt = 0;

	scanf("%d %d", &h, &w);
	for (i = 1; i <= h; i++) {
		for (j = 1; j <= w; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	scanf("%d %d", &x, &y);
	for (i = 1; i <= h; i++) {
		for (j = 1; j <= w; j++) {
			dp[i][j] = map[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
		}
	}
	for (i = x; i <= h; i++) {
		temp = 0;
		for (j = y; j <= w; j++) {
			temp = dp[i][j] - dp[i - x][j] - dp[i][j - y] + dp[i - x][j - y];
			if (temp > max) max = temp;
		}
	}
	printf("%d\n", max);
	return 0;
}

dp는 해당 행,열까지 모든 원소들의 합이다.

 

입력예시를 예를 들면,

 

입력받은 map은 다음과 같다

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

여기서 dp[1][1] = 3, dp[1][2] = 3 + 5 = 8, dp[2][1] = 3 + 1 = 4, dp[2][2] = 3 + 5 + 1+ 2 = 11 ...

 

dp를 구하면 다음과 같다

3	8	9	12	13	16	18
4	11	13	19	21	25	29
5	15	18	29	32	39	47
10	21	25	39	43	53	63
13	25	30	47	52	63	75
14	29	35	55	61	74	88

이를 다른 방법으로 표현 하면

 

2행 3열을 기준으로 보면

 

dp[2][3] (2행 3열까지의 전체합) = map[2][3] - 보라색 + 노란색이 될것이다.

 

dp[2][2] = map[2][2] - dp[1][2] - dp[2][1] + dp[1][1]

 

dp[3][3] = map[3][3] - dp[2][3] - dp[3][2] + dp[2][2]

 

...

 

dp[i][j] = map[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]

 

이런 식으로 구할 수 있다. 

 

또한 이 dp를 가지고 2차원 배열 구간합을 구할 수 있다.

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

예시의 정답인 3행 4열을 예시로 들어보면 현수가 얻을 수 있는 나무의 최대 개수는 빨간색으로 색칠한 부분의 합이다.

 

빨간색의 부분 합 = 4행6열까지의 전체합 - 파란색의 부분합 + 초록색의 부분합

 

으로 표현할 수 있다.

 

이를 dp에서 찾아보면 dp[4][6] = dp[4][6] - dp[3][4] - dp[2][6] + dp[2][3] 이 되는것을 알 수 있다.

 

이렇게 하면 두번의 2중 for문으로도 2차원 배열의 구간합을 구할수 있다.

 

.

 

이 개념이 완전히 DP(Dynamic Programming)은 아니라고 하시는데 유사한 방법이라고 함