[BOJ/백준][Gold3] 2571 : 색종이 - 3 (C++)

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

2571번: 색종이 - 3

 

 

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

[풀이]
map[100][100] 배열에 색종이가 있는 영역은 1로 채워 준 뒤

width : 1~100, height : 1~100 총 100 x 100개의 넓이에 대해서
(0,0) ~ (99,99) 을 왼쪽 끝 점으로 해서 만들 수 있는지를 브루트포스로 확인해주면 됩니다.

얼핏보면 100x100 x 100x100 x 100x100 = O(10^12) 으로 시간초과가 날 것 같지만
(0,0) ~ (99,99) 점에서 시작하는 직사각형을 만드는 과정이 생각보다 많은 시간이 들지 않습니다.
(코드에서는 bool check(int h,int w,int y,int x) 함수)

왜냐하면 넓이가 커지면 검사해야 하는 점이 줄어들고,
(예를들어 100x100인 경우 (0,0)만 검사하면 됨)

넓이가 작아지면 검사 시간이 적게 걸리기 때문입니다.
(예를들어 1x1인 경우 (0,0)~(99,99) 점을 검사해야 하지만 각각 1의 연산 밖에 들지 않음)

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,map[100][100];
bool check(int h,int w,int y,int x){
    for(int i=y;i<y+h;i++)
        for(int j=x;j<x+w;j++)
            if(!map[i][j]) return false;
    return true;
}
bool check(int h,int w){
    for(int i=0;i<=100-h;i++)
        for(int j=0;j<=100-w;j++)
            if(check(h,w,i,j)) return true;
    return false;
}
int main(){
    scanf("%d",&N);
    while(N--){
        int x,y;
        scanf("%d%d",&x,&y);
        for(int i=y;i<y+10;i++)
            for(int j=x;j<x+10;j++) map[i][j]=1;
    }
    int ans=0;
    for(int i=1;i<=100;i++)
        for(int j=1;j<=100;j++)
            if(check(i,j)) ans=max(ans,i*j);

    printf("%d",ans);
}

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