1451번

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

일단 총 여섯가지 케이스가 발생하게 된다.

그 중에서 나는 번호 매긴 것 처럼 1번과 2번은 getSumM1, getSumN1 으로 풀었다.

그리고 3,4,5,6번과 같은 경우는 선을 그은 것처럼 직사각형을 4분할 하였다.(getSum 함수)

그리고 각각 직사각형의 합을 구하였다. sum[0]~sum[3] 까지

그래서 왼쪽 상단을 0사분면, 오른쪽 상단을 1사분면, 왼쪽 하단을 2사분면, 오른쪽 하단을 3사분면이라고 한다면,

위의 3,4,5,6번 그림을 나타낼 수 있다. 

그래서 이를 통해서 최대값을 구해내는 방식으로 문제를 풀었다.

##문제점##

처음에는 1번,2번 그림을 N이 1일때, M이 1일때만 가능한 그림이라고 생각하여 실수를 저질렀다. 직사각형 네개로 모든 것을 표현할 수 있을 줄 알았다.

하지만 다시 생각해보니 가로로만 쪼개거나 , 세로로만 쪼개는 경우는 셀 수가 없었다.

그리고 값의 크기를 제대로 계산하지 않아서 int 형을 사용하는 실수를 범했다.

<정답 코드>

#include<iostream>
#include<algorithm>
 
using namespace std;
int N, M;
long long ans = 0;
int map[101][101];
 
void getSum(int x, int y, long long* sum)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (i >= 0 && i < x && j >= 0 && j < y)
            {
                sum[0] += map[i][j];
            }
            else if (i >= 0 && i < x&&j >= y&&j < M)
            {
                sum[1] += map[i][j];
            }
            else if (i >= x && i < N && j >= 0 && j < y)
            {
                sum[2] += map[i][j];
            }
            else if (i >= x && i < N && j >= y && j < M)
            {
                sum[3] += map[i][j];
            }
        }
    }
 
    return;
}
 
void getSumN1(int x, int y, long long *sum)
{
    for (int j = 0; j < N; j++)
    {
        for (int i = 0; i < M; i++)
        {
            if (i >= 0 && i < x)
            {
                sum[0] += map[j][i];
            }
            else if (i >= x && i < x + y)
            {
                sum[1] += map[j][i];
            }
            else
            {
                sum[2] += map[j][i];
            }
 
        }
    }
 
    return;
}
void getSumM1(int x, int y, long long *sum)
{
    for (int j = 0; j < M; j++)
    {
        for (int i = 0; i < N; i++)
        {
            if (i >= 0 && i < x)
            {
                sum[0] += map[i][j];
            }
            else if (i >= x && i < x + y)
            {
                sum[1] += map[i][j];
            }
            else
            {
                sum[2] += map[i][j];
            }
 
        }
    }
 
    return;
}
 
int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            char tmp;
            cin >> tmp;
            map[i][j] = tmp - '0';
        }
    }
 
    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = 1; j <= M - 1; j++)
        {
            long long sum[4] = { 0,0,0,0 };
            getSum(i, j, sum);
 
            long long ans1 = (sum[0] + sum[1])*sum[2] * sum[3];
            long long ans2 = (sum[0] + sum[2])*sum[1] * sum[3];
            long long ans3 = (sum[1] + sum[3])*sum[0] * sum[2];
            long long ans4 = (sum[2] + sum[3])*sum[0] * sum[1];
 
            ans = max({ ans,ans1,ans2,ans3,ans4 });
 
        }
    }
 
    for (int i = 1; i <= M - 2; i++)
    {
        for (int j = 1; i + j <= M - 1; j++)
        {
            long long sum[3] = { 0,0,0 };
            getSumN1(i, j, sum);
 
            ans = max(sum[0] * sum[1] * sum[2], ans);
        }
    }
 
    for (int i = 1; i <= N - 2; i++)
    {
        for (int j = 1; i + j <= N - 1; j++)
        {
            long long sum[3] = { 0,0,0 };
            getSumM1(i, j, sum);
 
            ans = max(sum[0] * sum[1] * sum[2], ans);
        }
    }
 
 
 
    cout << ans << endl;
 
    return 0;
}