[ boj : 1451 ] 직사각형으로 나누기

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

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

문제 : 직사각형이 주어지고 3등분의 직사각형으로 나눌때 각각의 합의 곱이 가장 큰 수를 구하시오

해설 : 처음 봤을때 어떻게 해야될지 순간 뇌절이 왔는데 직사각형을 그리다 보면 3가지로 나눌 수 있는 경우의 수는 6가지 밖에 없습니다.

각각 케이스에 해당하는 범위를 나누어서 구해주면 됩니다.(다만 이게 너무 머리가 꼬이니 침착하게 잘 조절하세요)

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int n, m;
ll sum[100][100],arr[100][100];

void show();

int main()
{
	
	string str;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> str;
		for (int j = 0; j < m; j++) {
			arr[i][j] = str[j] - '0';
		}
	}
	sum[0][0] = arr[0][0];
	for (int i = 1; i < n; i++) 
		sum[i][0] = sum[i - 1][0] + arr[i][0];	
	for (int i = 1; i < m; i++)
		sum[0][i] = sum[0][i - 1] + arr[0][i];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (i == 0 || j == 0)continue;
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
		}
	ll ans = 0;
	//가로 3줄
	for(int i=0;i<n;i++)
		for (int j = i + 1; j < n; j++)
		{
			ll x = sum[i][m - 1];
			ll y = sum[j][m - 1] - sum[i][m - 1];
			ll z = sum[n-1][m - 1] - sum[j][m - 1];
			ans = max(ans, x * y * z);
		}
	//세로 3줄
	for(int i=0;i<m;i++)
		for (int j = i + 1; j < m; j++)
		{
			ll x = sum[n-1][i];
			ll y = sum[n - 1][j] - sum[n - 1][i];
			ll z = sum[n-1][m - 1] - sum[n - 1][j];
			ans = max(ans, x * y * z);
		}
	//가로 2개블록 나누기
	for(int i=0;i<n-1;i++)
		for (int j = 0; j < m; j++)
		{
			ll x = sum[i][j];
			ll y = sum[i][m - 1] - sum[i][j];
			ll z = sum[n - 1][m - 1] - sum[i][m - 1];

			ll a = 
			ans = max(ans, x * y * z);
		}
	for(int i=n-1;i>0;i--)
		for (int j = 0; j < m; j++)
		{
			ll x = sum[n-1][j] - sum[i - 1][j];
			ll y = sum[n - 1][m - 1] - (sum[n-1][j] + sum[i - 1][m - 1]) + sum[i - 1][j];
			ll z = sum[i-1][m - 1];
			ans = max(ans, x * y * z);
		}
	//세로 2개블록 나누기
	for (int i = 0; i < m - 1; i++)
		for (int j = 0; j < n; j++)
		{
			ll x = sum[j][i];
			ll y = sum[n-1][i] - sum[j][i];
			ll z = sum[n - 1][m - 1] - sum[n-1][i];
			ans = max(ans, x * y * z);
		}
	for(int i=m-1;i>0;i--)
		for (int j = 0; j < n; j++)
		{
			ll x = sum[j][m-1] - sum[j][i - 1];
			ll y = sum[n - 1][m - 1] - (sum[j][m-1] + sum[n - 1][i - 1]) + sum[j][i - 1];
			ll z = sum[n - 1][i - 1];
			ans = max(ans,x * y * z);
		}
	cout << ans;
}