[코드트리 조별과제] 양수 직사각형의 최대 크기 C++ 풀이

---

알고리즘 분류

• 시뮬레이션

---

문제 설명

---

입력 설명

첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고, 두 번째 줄부터 (n+1)번째 줄까지는 각 행의 숫자가 공백을 사이에 두고 주어집니다.

• 1 ≤ n, m ≤ 20
• -1,000 ≤ 정수 값 ≤ 1,000

---

출력 설명

모든 값이 양수로만 이루어져 있는 직사각형 중 최대 크기를 출력해주세요. 만약 그러한 직사각형이 없다면, -1을 출력해주세요.

---

예제 입력

3 3
1 2 3
3 4 5
6 7 8

 

4 5
6 -2 4 -3 1
3 6 7 -4 1
6 1 8 15 -5
3 -5 1 16 3

---

예제 출력

9

 

6

---

아이디어

x1 ~ x2, y1 ~ y2 범위의 직사각형을 모두 체크하여 가장 큰 직사각형의 크기를 출력한다.

---

알고리즘

x1 ~ x2, y1 ~ y2 범위의 직사각형의 내부 원소가 모두 양수인지 판단한다.

내부 원소가 모두 양수라면 해당 직사각형의 크기를 측정하여 기존에 측정한 최대 크기보다 크다면 이를 저장한다.

최대 직사각형의 크기가 0이라면 -1을 출력하고 아니라면 그대로 출력한다.

---

코드

#include <iostream>
#include <vector>
using namespace std;
bool check(vector<vector<int>> &vec, int x1, int x2, int y1, int y2)
{
    for(int i = x1; i <= x2; i++)
    {
        for(int j = y1; j <= y2; j++)
        {
            if(vec[i][j]==0) return false;
        }
    }
    return true;
}
int count(int x1,int x2,int y1,int y2)
{
    int cnt=0;
    for(int i = x1; i <= x2; i++)
    {
        for(int j = y1; j <= y2; j++)
        {
            cnt++;
        }
    }
    return cnt;
}

int main() {
    int n, m,temp,max=0;
    cin>>n>>m;
    vector<vector<int>> vec(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>temp;
            if(temp>0) vec[i][j] = 1;
            else vec[i][j] = 0;
        }
    }

    for(int i = 1; i<=n; i++)
    {
        for(int j = 1; j <=m; j++)
        {
            for(int x = i; x<=n; x++)
            {
                for(int y = j; y <=m; y++)
                {
                    if(check(vec, i, x, j, y))
                    {
                        int temp = count(i, x, j, y);
                        if(max < temp) max = temp;
                    }
                }
            }
        }
    }
    if(max == 0) cout<<-1;
    else cout<<max;
    return 0;
}

---

후기

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

항상 백준 문제만 풀다가 처음으로 코드트리 문제를 풀어봤다.

커리큘럼이 정해져있어서 좋았다.

앞으로도 둘 다 병행하면서 풀어야겠다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!