(c++)백준 1451번: 직사각형으로 나누기

https://www.acmicpc.net/problem/1451

1451번: 직사각형으로 나누기

[풀이]

직사각형을 세 개의 직사각형으로 나누는 경우는 아래와 같이 6가지가 있다

세 개의 직사각형은 모두 같은 크기일 필요가 없으므로 위의 모양들 각각으로 자르는 경우 안에서도 가능한 모든 경우의 수를 찾아봐야 한다.

 

#include <iostream>
#include <algorithm>//max
#include <cstdio>//scanf
using namespace std;

int N, M; 
int Num[101][101];
long long Max = -1;

int getSum(int startx, int starty, int endx, int endy) {
	int sum = 0;
	for (int i = startx; i <= endx; i++) {
		for (int j = starty; j <= endy; j++) {
			sum += Num[i][j];
		}
	}
	return sum;
}

void solution() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &Num[i][j]);
		}
	}
	
	//1번 모양
	for (int i = 0; i < N - 2; i++) {
		for (int j = i + 1; j < N - 1; j++) {
			long long square1 = getSum(0, 0, i, M - 1);
			long long square2 = getSum(i + 1, 0, j, M - 1);
			long long square3 = getSum(j + 1, 0, N - 1, M - 1);
			Max = max(Max, square1*square2*square3);
		}
	}

	//2번 모양
	for (int i = 0; i < M - 2; i++) {
		for (int j = i + 1; j < M - 1; j++) {
			long long square1 = getSum(0, 0, N - 1, i);
			long long square2 = getSum(0, i + 1, N - 1, j);
			long long square3 = getSum(0, j + 1, N - 1, M - 1);
			Max = max(Max, square1*square2*square3);
		}
	}

	//3번 모양
	for (int i = M - 1; i > 0; i--) {
		for (int j = 0; j < N - 1; j++) {
			long long square1 = getSum(0, i, N - 1, M - 1);
			long long square2 = getSum(0, 0, j, i - 1);
			long long square3 = getSum(j + 1, 0, N - 1, i - 1);
			Max = max(Max, square1*square2*square3);
		}
	}

	//4번 모양
	for (int i = 0; i < M - 1; i++) {
		for (int j = 0; j < N - 1; j++) {
			long long square1 = getSum(0, 0, N - 1, i);
			long long square2 = getSum(0, i + 1, j, M - 1);
			long long square3 = getSum(j + 1, i + 1, N - 1, M - 1);
			Max = max(Max, square1*square2*square3);
		}
	}

	//5번 모양
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < M - 1; j++) {
			long long square1 = getSum(0, 0, i, M - 1);
			long long square2 = getSum(i + 1, 0, N - 1, j);
			long long square3 = getSum(i + 1, j + 1, N - 1, M - 1);
			Max = max(Max, square1*square2*square3);
		}
	}

	//6번 모양
	for (int i = N - 1; i > 0; i--) {
		for (int j = 0; j < M - 1; j++) {
			long long square1 = getSum(i, 0, N - 1, M - 1);
			long long square2 = getSum(0, 0, i - 1, j);
			long long square3 = getSum(0, j + 1, i - 1, M - 1);
			Max = max(Max, square1*square2*square3);
		}
	}
	cout << Max << endl;
}

int main() {
	solution();
	return 0;
}