[코드트리] 양수 직사각형의 최대 크기 C++

문제

https://www.codetree.ai/missions/2/problems/max-area-of-positive-rectangle?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

계획 세우기

어제 풀었던 겹쳐지지 않는 두 직사각형이랑 비슷한데 좀 더 쉬운 느낌이다.

1. 점을 선택 + 사각형의 너비와 높이를 설정한다.
2. 해당 사각형에 속하는 곳의 갯수를 더하다가 0이나 음수가 있으면 -1 반환, 없으면 갯수를 반환
3. 최대값 갱신

 

풀이

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int answer=-1;
int arr[21][21];

int CheckRectangle(int x1, int y1, int x2, int y2){
    int cnt=0;
    for(int i=x1; i<=x2; i++){
        for(int j=y1; j<=y2; j++){
            if(arr[i][j]<=0) return -1;
            cnt++;
        }
    }
    return cnt;
}

void PointToStart(){
    // (i,j)점에서 width, height 사각형 만들기
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){

            for(int width=0; width<m; width++){
                for(int height=0; height<n; height++){
                    if(j+width>m || i+height>n) continue;
                    answer = max(answer, CheckRectangle(i, j, i+height, j+width));
                }
            }
            
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> arr[i][j];
        }
    }
    PointToStart();
    cout << answer<<'\n';
    return 0;
}