[알골90제] 50/51번 - 브루트포스/다이나믹프로그래밍 : 오렌지나무 territory 선택 (small/big)

*문제

 

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

 

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

 

---

*문제 읽기

 

1) 가로 * 세로 길이의 territory 크기를 입력받는다. (5<=H, W<=50)

2) territory 의 각 영역안에 오렌지나무의 개수를 입력받는다. (1~9)

3) 현수가 받을 크기의 땅 입력받기 

4) 현수가 얻을 수 있는 오렌지 나무의 최대 개수 출력

 

*생각

 

1) 배열에 입력 다 받는 건 OK

2)해당영역이 최대 개수의 오렌지 나무를 가지는지 알아봐야 함

3)이중 가장 큰값을 구함 temp써서 최대값 구하고 max인지 확인한 후 max가 맞으면 집어 넣기

 

 

SMALL 풀이 방법 - 브루트포스

 

*코드 구현

 

// 50번 - territory 선택 (small)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int a[51][51];

int main() {

	//freopen("input.txt", "rt", stdin);
	int h, w, n, m, sum, max=-999999999;
	scanf("%d %d", &h, &w);

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			scanf("%d", &a[i][j]);
		}
	}

	scanf("%d %d", &n, &m);

	for (int i = 0; i < h-n+1; i++) {
		for (int j = 0; j < w-m+1; j++) {
			sum = 0;
			for (int k = i; k < i + n; k++) {
				for (int s = j; s < j + m; s++) {
					sum = sum + a[k][s];
				}
			}
			if (sum > max) max = sum;
		}
	}

	printf("%d\n", max);
}

- 영지 territory의 크기 h와 w를 입력받고 그만큼 수를 채워 넣음

- 4중 for문이 돌면서 일일이 다 세는 것

 

 

*풀이

 

1) 4중 for문을 써야함.

2)

2*3 다 더하면 됨

 

 

 

 

 

3)

노란지점까지 다 더하면됨.

그 이후는 영역을 벗어나버리니깐

 

 

 

 

 

 

 

 

 

* 수가 적다면 4중 for문으로 주어진 행렬에서 일부 행렬의 합을 구할 수 있다.
* i / j 에서 영역이 튀어나가지 않게 더해주는 것이 중요. 일부행렬의 크기를 고려하여 어디까지 for문을 돌지 잘 염두해둬야 함

 

 

---

 

 

LARGE 풀이 방법 - 다이나믹 프로그래밍(DP)

=> 앞서 사용했던 4중 for문을 2중 for문으로 줄일 수 있다.

 

*풀이: 

 

1) 다이나믹 프로그래밍 테이블을 만든다.

- 읽으면서 누적한다.

 

2) 다음 행은 다른 방법으로 누적이다.

3) 다이나믹 값을 구하는 식

- 점 찍은 곳은 핑크 사각형의 총 합임

- 다이나믹 프로그래밍 테이블의 18 값은 왼쪽의 원래 배열에서의 핑크색 박스의 합

 

 

 

- 점찍은 곳 구하는 방법 : 18+19

- 우리가 구하고자 하는 값: 초록

 

- 검은색 부분이 교집합은 빼줘야 한다.

왜냐하면 18과 19 자리를 구할 때 2번 더해진 부분이기 때문이다. 그렇기 때문에 그만큼 교집합 부분을 1번 빼줘야한다.

- 최종 연산: 18 + 19 - 13 + 5

13: 교집합 부분(중복된 부분)

5: 새로 합해야하는 부분(현재 scanf로 읽혀지는 a행렬의 값)

- 식으로 표현하면 

dy[i][j] = dy[i][j-1] + dy[i-1][j] - dy[i-1][j-1] + a[i][j]

- 첫줄이나 그런 부분들은 누적 0으로 계산한다.

 

- 검은 영역 부분을 구하려면 다이나믹프로그래밍 테이블의 53번째를 이용해야함(누적된 것이니깐)

- 근데 1.1부터 쭉~~누적해온것이기 때문에 영지의 크기만큼 그 전까지의 사각형을 빼줘야한다.

- 영지의 크기 2*3이기 때문에 53위치에서 각각 i-2 / j-3 해준 부분을 빼준다.

- 교집합을 2번빼게 되기 때문에 다시 한번 더 해줘야한다.

dy[i][j] - dy[i-2][j] - dy[i][j-3] + dy[i-2][j-3] 

 

 

- 주의 할 점은 dy테이블은 이미 누적이기 때문에 1.1부터 구하는게 아니라 입력된 territory의 크기 만큼 누적된 그 끝부터 돌게 됨

 

n과 m부터 돌아야한다.

 

 

- dy테이블에서 최대 오렌지나무 영역 구하는 부분 재설명

 

 

*코드구현

 

// 51번 - territory 선택 (large) 다이나믹 프로그래밍
// small 4중 for문에서 => 2중 for문으로


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int a[701][701];
int dy[701][701]; //추가

int main() {

	freopen("input.txt", "rt", stdin);
	int h, w, n, m, sum, max = -999999999;
	scanf("%d %d", &h, &w);

	//1부터 시작해야 이전 값 0을 더할 수 있음
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			scanf("%d", &a[i][j]);
			//추가: 읽으면서 dy테이블 만들기
			//주의: 현재값 a[i][j]를 더해주는 것 잊지말기
			dy[i][j] = dy[i - 1][j] + dy[i][j - 1] - dy[i - 1][j - 1] + a[i][j];
		}
	}

	scanf("%d %d", &n, &m);

	//시작을 2행 3열부터 해야함
	for (int i = n; i <=h; i++) {
		for (int j = m; j <=w; j++) {
			//주어진영역의 합
			sum = dy[i][j] - dy[i - n][j] - dy[i][j - m] + dy[i - n][j - m];
			if (sum > max) max = sum;
		}
	}

	printf("%d\n", max);
}

 

 

기억할 것

* 입력값을 읽으면서 다이나믹 프로그래밍 테이블을 만들 수 있다. (누적값 계산) - 중복값 빼고 현재값 더해주는 것 잊지않기!
* 다이나믹 프로그래밍 테이블을 따로 만들어 줘야한다.
* 누적 값이 계산되는 것이기 때문에 교집합으로 중복덧셈이나 중복 뺄셈이 있는지 확인해줘야 한다.
* 다이나믹 프로그래밍 테이블의 일부를 덧셈할 때는 for문의 시작점을 잘 봐야한다.