[백준] 색종이 - 3

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

2571번: 색종이 - 3

N^6 로직을 활용하여 해결하였습니다.

 

우선 문제부터 간단하게 요약하면, 

흰 도화지 위에 검정 색종이를 붙입니다. 이 때, 검정색 부분을 가장 큰 직사각형 모양으로 잘라내고 싶을 때, 잘라낼 수 있는 가장 큰 넓이를 구해야 합니다.

 

<Solution>

도화지의 크기가 크지 않으므로, 

시작지점(N^2)과 끝지점(N^2)을 찾아서, 해당하는 구간이 모두 검정색이 맞는지 탐색(N^2)을 하면서 만약 맞다면 area의 넓이를 계산해서 갱신해주는 방식으로 구현을 하였습니다.

 

이렇게 하면 알고리즘의 시간 복잡도가 N^6으로 비효율적입니다. N^3 또는 N^2으로 하는 방식도 있다고 하는데, 조만간 다시 풀어서 추가할 예정입니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>
using namespace std;
int N;//색종이 수
int X[100+10];
int Y[100+10];
void InputData() {
    cin >> N;
    for (int i=0; i<N; i++){
        cin >> X[i] >> Y[i];
    }
}
 
char grid[100+10][100+10];
void fill(int r, int c){
    for(int i = 0; i<10; i++){
        for(int j=0;j<10;j++){
            grid[r+i][c+j] = '1';
 
        }
    }
}
 
int calculate_area(int r1, int c1, int r2, int c2){
 
    for(int i = r1; i<=r2; i++){
        for(int j = c1; j<=c2; j++){
            if(grid[i][j] !='1') return -1;
        }
    }
 
    return (r2-r1+1) * (c2-c1+1);
}
 
 
int solution(){
    // fill grid
    for(int i = 0; i<N; i++){
        fill(X[i]+1, Y[i]+1);
    }
 
    // find out max area
    int max_area = 0;
    for(int r1 = 1; r1<=100; r1++){
        for(int c1= 1; c1<= 100; c1++){
             
            if(grid[r1][c1] != '1') continue;
 
            for(int r2 = r1; r2<=100; r2++){
                for(int c2 = c1; c2 <= 100; c2++){
                    if(grid[r1][c1] != '1') continue;
                    max_area = max(calculate_area(r1,c1,r2,c2), max_area);
 
 
                }
            }
 
        }
    }
    return max_area;
 
}
 
 
int main() {
    int ans = -1;
    InputData();//입력받는 부분
     
    //여기서부터 작성
    ans = solution();
     
    cout << ans << endl;//출력하는 부분
    return 0;
}