[백준문제풀이] 1451 직사각형으로 나누기

 

풀이일시 : 2020-10-15

​

 

문제 :

세준이는 N*M크기로 직사각형에 수를 N*M개 써놓았다.

세준이는 이 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누려고 한다. 각각의 칸은 단 하나의 작은 직사각형에 포함되어야 하고, 각각의 작은 직사각형은 적어도 하나의 숫자를 포함해야 한다.

어떤 작은 직사각형의 합은 그 속에 있는 수의 합이다. 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나누었을 때, 각각의 작은 직사각형의 합의 곱을 최대로 하는 프로그램을 작성하시오.

​

 

입력 :

첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다.

ex)

1 8

1 1 9 1 1 1 0 3

​

 

출력 :

세 개의 작은 직사각형의 합의 곱의 최댓값을 출력한다.

ex)

108

​

 

풀이 :

입력의 예시

3x5 직사각형을 다음과 같이 나눌 수도 있다. 물론 나누는 방법은 매우 많을것이다. 직사각형을 나눠보고 그 안의 숫자를 더한 후 각 직사각형끼리의 곱을 비교하려면 모든 방법으로 수행해봐야 될 것이다. 따라서 BP이다.

사각형을 세개로 나누는 방법은 총 6가지 방법이 있다.

 

case 1:

case 2:

case 3:

case 4:

case 5:

case 6:

case를 6개로 나누어 모두 탐색해준다. 그 중 최대의 값을 return 하면 될것이다.

 

#include <iostream>
using namespace std;

int arr[101][101] = { 0, };
long long MAX = 0;

long long sum(int sx, int sy, int ex, int ey) {
	long long ret = 0;
	for (int i = sy; i <= ey; i++) {
		for (int j = sx; j <= ex; j++) {
			ret += arr[i][j]; //합해준다.
		}
	}
	return ret;
}

int main() {
	int N, M, s;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf_s("%1d", &s); //한글자씩 input받는 방법
			arr[i][j] = s;
		}
	}
	//직사각형을 나누는 방법은 총 6가지이다.
	//각 꼭지점의 인덱스를 알고 sum에 들어가자

	// 1번 case
	for (int i = 0; i < M - 2; i++) {
		for (int j = i + 1; j < M - 1; j++) {
			long long a = sum(0, 0, i, N - 1);
			long long b = sum(i + 1, 0, j, N - 1);
			long long c = sum(j + 1, 0, M - 1, N - 1);
			if (MAX < a * b * c)
				MAX = a * b * c;
		}
	}

	// 2번 case
	for (int i = 0; i < N - 2; i++) {
		for (int j = i + 1; j < N - 1; j++) {
			long long a = sum(0, 0, M - 1, i);
			long long b = sum(0, i + 1, M - 1, j);
			long long c = sum(0, j + 1, M - 1, N - 1);
			if (MAX < a * b * c)
				MAX = a * b * c;
		}
	}

	// 3번 case
	for (int i = 0; i < M - 1; i++) {
		for (int j = 0; j < N - 1; j++) {
			long long a = sum(0, 0, i, N - 1);
			long long b = sum(i + 1, 0, M - 1, j);
			long long c = sum(i + 1, j + 1, M - 1, N - 1);
			if (MAX < a * b * c)
				MAX = a * b * c;
		}
	}

	// 4번 case
	for (int i = M - 1; i > 0; i--) {
		for (int j = 0; j < N - 1; j++) {
			long long a = sum(i, 0, M - 1, N - 1);
			long long b = sum(0, 0, i - 1, j);
			long long c = sum(0, j + 1, i - 1, N - 1);
			if (MAX < a * b * c)
				MAX = a * b * c;
		}
	}

	// 5번 case
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < M - 1; j++) {
			long long a = sum(0, 0, M - 1, i);
			long long b = sum(0, i + 1, j, N - 1);
			long long c = sum(j + 1, i + 1, M - 1, N - 1);
			if (MAX < a* b* c)
				MAX = a * b * c;
		}
	}

	// 6번 case
	for (int i = N - 1; i > 0; i--) {
		for (int j = 0; j < M - 1; j++) {
			long long a = sum(0, i, M - 1, N - 1);
			long long b = sum(0, 0, j, i - 1);
			long long c = sum(j + 1, 0, M - 1, i - 1);
			if (MAX < a * b * c)
				MAX = a * b * c;
		}
	}

	//만약 long long 타입을 출력하고자하면 lld로 써야한다.

	printf("%d", MAX);
	//cout << MAX << endl;
	return 0;

}

 

참고자료 : input방법들

dbstndi6316.tistory.com/33

[개념정리] C++ 여러 input방법에 대해