[코드트리 조별과제] 잔해물을 덮기 위한 사각형의 최소 넓이 C++ 풀이

---

알고리즘 분류

• 구현
• 시뮬레이션

---

문제 설명

첫 번째 직사각형이 먼저 놓여 있고, 두 번째 직사각형이 그다음 놓아졌을 때 그 이후에 남아있는 첫 번째 직사각형의 잔해물을 덮기 위한 최소 직사각형의 넓이를 구하는 프로그램을 작성해 보세요.

---

입력 설명

첫 번째 줄에 첫 번째 직사각형에 해당하는 좌측하단의 좌표와 우측상단의 좌표 (x1, y1), (x2, y2)가 공백을 사이에 두고 주어집니다.

두 번째 줄에 두 번째 직사각형에 해당하는 좌측하단의 좌표와 우측상단의 좌표 (x1, y1), (x2, y2)가 공백을 사이에 두고 주어집니다.

• -1,000 ≤ x1 < x2 ≤ 1,000
• -1,000 ≤ y1 < y2 ≤ 1,000

---

출력 설명

첫 번째 줄에 남아있는 첫 번째 직사각형의 잔해물을 덮기 위한 최소 직사각형의 넓이를 출력합니다.

---

예제 입력

2 1 7 4
5 -1 10 3

---

예제 출력

15

---

아이디어

0으로 초기화된 2차원 배열에 첫 번째 직사각형을 1로 칠한다.

그리고 두 번째 직사각형을 다시 0으로 칠한다.

1로 남은 부분 중 가로와 세로의 최대 길이를 구하여 곱하고 출력한다.

---

알고리즘

0으로 초기화된 2차원 배열에 첫 번째 직사각형을 1로 칠한다.

그리고 두 번째 직사각형을 다시 0으로 칠한다.

첫 번째 2중 for문의 바깥은 세로줄을 탐색하고 안쪽은 가로줄을 탐색한다.

두 번째 2중 for문의 바깥은 가로줄을 탐색하고 안쪽은 세로줄을 탐색한다.

첫 번째 2중 for문에서 안쪽의 가로줄을 탐색하는 for문을 2개 즉, 왼쪽에서 오른쪽으로 가는 for문과 오른쪽에서 왼쪽으로 가는 for문으로 가로줄의 최대 길이를 구한다. 이때 가로줄을 항상 연속되지 않아도 된다.

두 번째 2중 for문에서 안쪽의 세로줄을 탐색하는 for문을 2개 즉, 위쪽에서 아래쪽으로 가는 for문과 아래쪽에서 위쪽으로 가는 for문으로 세로줄의 최대 길이를 구한다. 이때 세로줄을 항상 연속되지 않아도 된다.

만약 가로줄이나 세로줄이 존재하지 않는다면 0을 출력하고 존재한다면 두 값의 곱인 최소 직사각형의 넓이를 출력한다.

---

코드

#include <iostream>
using namespace std;
bool empty;
int maxga(bool arr[2001][2001])
{
    int maxga=0; empty=true;
    for(int i=2000,g1=0,g2=0;i>=0;i--)
    {
        for(int j=2000;j>=0;j--)
        {
            if(arr[i][j] == true)
            {
                g1 = j;
                empty = false;
                break;
            } 
        }
        for(int j=0;j<2001;j++)
        {
            if(arr[i][j] == true) 
            {
                g2 = j;
                break;
            } 
        }
        if((g1-g2+1)>maxga) maxga = (g1-g2+1);
    } 
    return maxga;
}
int maxse(bool arr[2001][2001])
{
    int maxse=0;
    for(int i=2000,s1=0,s2=0;i>=0;i--)
    {
        for(int j=2000;j>=0;j--)
        {
            if(arr[j][i] == true)
            {
                s1 = j;
                empty = false;
                break;
            } 
        }
        for(int j=0;j<2001;j++)
        {
            if(arr[j][i] == true) 
            {
                s2 = j;
                break;
            } 
        }
        if((s1-s2+1)>maxse) maxse = (s1-s2+1);
    } 
    return maxse;
}
int main() {
    int a1,b1,c1,d1,a2,b2,c2,d2;
    cin>>a1>>b1>>c1>>d1>>a2>>b2>>c2>>d2;
    bool arr[2001][2001] = {0,};
    a1+=1000,b1+=1000,c1+=1000,d1+=1000,a2+=1000,b2+=1000,c2+=1000,d2+=1000;
    for(int i=d1;i>b1;i--)
        for(int j=c1;j>a1;j--)
            arr[i][j]=1;
    for(int i=d2;i>b2;i--)
        for(int j=c2;j>a2;j--)
            arr[i][j]=0;
    int semax = maxse(arr);
    int gamax = maxga(arr);
    if(empty) cout<<0;
    else cout<<(gamax*semax);
    return 0;
}

---

후기

문제 링크 -> https://www.codetree.ai/missions/5/problems/minimum-area-of-rectangle-to-cover-debris?&utm_source=clipboard&utm_medium=text

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

마지막에 최소 직사각형의 넓이를 구하는 방법을 생각하는 것이 조금 어려웠지만

깊게 고민하여 알아낼 수 있었다.

---

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

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