백준 2628 종이자르기(c++)

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

2628번: 종이자르기

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int n,m,t;
	cin>>n>>m;
	cin>>t; // 자르는 횟수
	vector<int>width(n); // 가로 
	vector<int>length(m); // 세로  
	for(int i=0;i<t;i++)
	{
		int a,b;
		cin>>a>>b;
		if(a==0) length.push_back(b);
		if(a==1) width.push_back(b);
	}
	width.push_back(n);
	length.push_back(m);
	sort(length.begin(),length.end());
	sort(width.begin(),width.end());
	int result =0;
	if(length.size()==1 && width.size()>1)
	{
		for(int j=1;j<width.size();j++)
		{
			if(length[0] * (width[j]-width[j-1])>result){
				result = length[0] * (width[j]-width[j-1]);
			}
		}
			cout<<result;	
	}
	else if(length.size()>1 && width.size()>1){
	for(int i=1;i<length.size();i++)
	{
		for(int j=1;j<width.size();j++)
		{
			if((length[i]-length[i-1])*(width[j]-width[j-1])>result){
				result = (length[i]-length[i-1])*(width[j]-width[j-1]);
			}
		}
	}
		cout<<result;
	}
	else if(length.size()>1 && width.size()==1)
	{
		for(int j=1;j<length.size();j++)
		{
			if(width[0] * (length[j]-length[j-1])>result){
				result = length[0] * (width[j]-width[j-1]);
			}
		}
		cout<<result;
	}
	else{
		cout<<width[0]*length[0];
	}
	
	
}

<풀이과정>

잘린 가로의 길이의 최대 * 잘린 세로의 길이의 최대 => 최대 사각형의 넓이 

그렇지만 가로와 세로가 잘리지 않은 경우도 고려해야 되기 때문에, if문을 통해 각 조건을 나누어주었다.

1.length.size()==1 && width.size()>1 =>가로 한번이상 자르고, 세로 자르지 않음

2.length.size()>1 && width.size()>1 => 가로 한번이상 자르고, 세로 한 번 이상 자름

3.length.size()>1 && width.size()==1 => 세로 한번이상 자르고, 가로 자르지 않음

4.else => 둘 다 자르지 않음