[boj : 2571] 색종이 자르기 - 3

www.acmicpc.net/problem/2571

2571번: 색종이 - 3

문제 : 색종이를 여러개 겹쳐서 가장 큰 직사각형의 넓이를 구해라

 

해설 : 직사각형은 전부 선분이 일직선이여야 되니 될수 있는 경우의 수를 다 해주었다.

판의 최대 크기는 100이니 직사각형의 가로/세로의 길이를 1부터 시작해서 100까지 늘려주면서 해당하는 직사각형을 그릴 수 있는지 판별해 주었다.

#include<bits/stdc++.h>

using namespace std;

int board[101][101], v[101][101];

int find(int x, int y);
int getans(int x, int y, int h, int w);
void draw(int x, int y);

int main()
{
	int t;
	cin >> t;
	int x, y;
	for (int i = 0; i < t; i++) {
		cin >> x >> y;
		draw(x, y);
	}
	
	int ans = 100;
	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= 100; j++)
			if (board[i][j] == 1)
				ans = max(ans,find(i, j));
	cout << ans;	
	return 0;
}
int find(int x,int y)
{
	int ans = 100;
	for (int i = 0; i <= 100; i++) {
		if (x + i > 100)break;
		for (int j = 0; j <= 100; j++) {
			if (y + j > 100)break;
			ans = max(ans, getans(x, y, x + i, y + j));
		}
	}
	return ans;
}
int getans(int x, int y, int h, int w)
{
	int cnt = 0;
	for(int i=x;i<=h;i++)
		for (int j = y; j <= w; j++) {
			if (board[i][j] == 0)
				return 0;
			else
				cnt++;
		}
	return cnt;
}
void draw(int x, int y)
{
	for (int i = x; i < x + 10; i++)
		for (int j = y; j < y + 10; j++)
			board[i][j] = 1;
}