[BOJ/백준][Gold5] 1451 : 직사각형으로 나누기 (C++)

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

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

 

 

[난이도] Gold5
[유형] 브루트포스

[풀이]
직사각형 3개로 나눌 수 있는 모양은 총 6가지가 나옵니다.
수평, 혹은 수직으로 3개로 나누는 2개 이외에,
ㅏ ㅓ ㅜ ㅗ 모양의 4가지 모양이 더 있을 수 있다는 것을 주의해야 합니다.
N,M 제한이 50밖에 되지 않으므로,
2중, 3중 for문을 적절히 활용해서 구간을 나누어 브루트포스로 구해주면 됩니다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
int N,M;
ll a[50][50];
ll sol(int sy,int sx,int ey,int ex){
    ll sum=0;
    for(int i=sx;i<=ex;i++)
        for(int j=sy;j<=ey;j++)
            sum+=a[j][i];
    return sum;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf("%1lld",&a[i][j]);

    ll ans=0;
    for(int i=0;i<N-2;i++)
        for(int j=i+1;j<N-1;j++)
            ans=max(ans,sol(0,0,i,M-1)*sol(i+1,0,j,M-1)*sol(j+1,0,N-1,M-1));

    for(int i=0;i<M-2;i++)
        for(int j=i+1;j<M-1;j++)
            ans=max(ans,sol(0,0,N-1,i)*sol(0,i+1,N-1,j)*sol(0,j+1,N-1,M-1));

    for(int i=0;i<N-1;i++){
        for(int j=0;j<M-1;j++) ans=max(ans,sol(0,0,i,M-1)*sol(i+1,0,N-1,j)*sol(i+1,j+1,N-1,M-1));
        for(int j=0;j<M-1;j++) ans=max(ans,sol(i+1,0,N-1,M-1)*sol(0,0,i,j)*sol(0,j+1,i,M-1));
    }
    for(int i=0;i<M-1;i++){
        for(int j=0;j<N-1;j++) ans=max(ans,sol(0,0,N-1,i)*sol(0,i+1,j,M-1)*sol(j+1,i+1,N-1,M-1));
        for(int j=0;j<N-1;j++) ans=max(ans,sol(0,i+1,N-1,M-1)*sol(0,0,j,i)*sol(j+1,0,N-1,i));
    }
    printf("%lld",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1451.cpp