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

문제

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

행 n과 열 m이 주어지면 n*m 직사각형을 세등분으로 나누어 세 직사각형 넓이의 곱의 최대를 출력해주면 됩니다.

각 직사각형의 넓이는 각 직사각형의 포함되는 n*m 이차원 배열의 인덱스 값의 합입니다.

저는 처음에 생각했을 때 세 직사각형의 넓이의 곱이 최대로 될려면 각 직사각형이 전체 n * m 넓이의 평균에

가까울 수록 넓이가 커진다고 생각했습니다.

따라서 1)번으로 생각했습니다.

1) 모든 수를 더하면서 평균값에 가깝게 직사각형을 묶음

2) 직사각형을 어떻게 나누는지 구현?

하지만 2)번에 막혀 버려서 여러 블로그글들을 찾아봤습니다.

 

관건은 직사각형을 삼등분하는 방법은 총 6가지가 존재 해서 모든 경우의 수를 봐주는 것입니다.

 

먼저 n*m 직사각형을 삼등분하기 전에 prefix sum방법으로 직사각형의 누적합을 기록하였습니다.

1~6 번째 줄까지는 입력 부분입니다.

7~9 번째 줄은 prefix sum 을 처리해 주는 과정입니다.

 

이제 n * m 직사각형을 삼등분하는 경우의 수입니다.

1) | |

 

2) =

 

3) ㅗ

 

4) ㅜ

 

5) ㅏ

 

6) ㅓ

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n,m;
string st;
int arr[51][51];
int psum[51][51];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>st;
        for(int j=1;j<=m;j++)
            arr[i][j] = st[j-1] - '0';
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+arr[i][j];
 
    ll ret=0;
    ll s1, s2, s3;
    for(int i=1;i<=m-2;i++){
        for(int j=i+1;j<=m-1;j++){
            s1=psum[n][i];
            s2=psum[n][j]-s1;
            s3=psum[n][m]-(s1+s2);
            ret = max(ret, s1 * s2 * s3);
        }
    }        
    for(int i=1;i<=n-2;i++){
        for(int j=i+1;j<=n-1;j++){
            s1=psum[i][m];
            s2=psum[j][m]-s1;
            s3=psum[n][m]-(s1+s2);
            ret = max(ret, s1 * s2 * s3);
        }
    }    
    for(int i=1;i<=m-1;i++){ //ㅗ
        for(int j=n-1;j>=1;j--){
            s1=psum[n-j][m]-psum[n-j][i];
            s2=psum[n][m]-psum[n-j][m];
            s3=psum[n][m]-(s1+s2);
            ret=max(ret,s1*s2*s3);
        }
    }
    for(int i=1;i<=n-1;i++){ //ㅜ
        for(int j=1;j<=m-1;j++){
            s1=psum[i][m];
            s2=psum[n][j]-psum[i][j];
            s3=psum[n][m]-(s1+s2);
            ret = max(ret, s1 * s2 * s3);
        }
    }
    for(int i=1;i<=m-1;i++){ //ㅏ
        for(int j=1;j<=n-1;j++){
            s1=psum[n][i];
            s2=psum[j][m]-psum[j][i];
            s3=psum[n][m]-(s1+s2);
            ret = max(ret, s1 * s2 * s3);
        }
    }
    for(int i=1;i<=n-1;i++){ //ㅓ
        for(int j=1;j<=m-1;j++){
            s1=psum[n][j]-psum[i][j];
            s2=psum[n][j]-s1;
            s3=psum[n][m]-(s1+s2);
            ret = max(ret, s1 * s2 * s3);
        }
    }
    cout<<ret;
 
 
 
    
    return 0;
}