[백준] C++ 1744(수 묶기)

#include <iostream>
#include <algorithm>

using namespace std;

int arr[51];
int arr2[51];
int main(void)
{
	int a=0;
	cin>>a;
	
	int count1=0;
	int count2=0;
	
	for(int i=0; i<a; i++)
	{
		int num=0;
		cin>>num;
		if(num>0)
		{
			arr[count1]=-num;
			count1++;
		}
		else
		{
			arr2[count2]=num;
			count2++;
		}
	}
	
	sort(arr,arr+count1);
	sort(arr2,arr2+count2);
	
	int sum=0;
	
	
	for(int i=0; i<count1; i=i+2)
	{
		int num1=-arr[i];
		int num2=-arr[i+1];
		
		if((num1==1||num2==1))
		{
			sum=sum+num1+num2;
		}
		else
		{
			if(count1==1||i==count1-1)
			{
				sum=sum+num1;
			}
			else
			{
				sum=sum+num1*num2;
			}
		}
	}
	
	for(int i=0; i<count2; i=i+2)
	{
		int num1=arr2[i];
		int num2=arr2[i+1];
		
		if(i==count2-1)
		{
			sum=sum+num1;
		}
		else
		{
			sum=sum+num1*num2;
		}
		
	}
	
	cout<<sum;
		
	return 0;
}

 

이 문제는 수를 효율적으로 묶어 합이 최대가 되게 만들어야 한다. 

이 문제는 생각보다 조건이 많이 필요하다.

1.양수*양수일 때 최대가 되려면??

2.양수*1이면??

3.0은 어떻게 사용하는가??

4.음수*음수는 언제가 최대지??

 

1에 대한 대답은 양수*양수가 최대가 되게 하려면 양수를 높은 순으로 정렬한 뒤 곱해주어야 한다.

2에 대한 대답은 양수*1의 값은 양수+1의 값보다 작다 만약 1이 나온다면 양수+1을 해주어야 한다.(예 3*1=3   3+1=4 )

(1*1=1   1+1=2)

3에 대한 대답은 0은 남은 음수와 곱해주는게 best이다. 음수*음수를 하면 양수가 된다. 그런데 음수가 홀수개인 경우에는?? 만약 0이 있다면 음수*0을 해줘서 0으로 만드는게 더 이득이다.

4에 대한 대답은 음수*음수가 최대가 되게 하려면 음수를 작은 순으로 정렬해주면 된다.(예 -9, -5, -8, -2 =   (-9*-8)+(-5*-2))

 

나는 음수와 양수를 분리하여 문제를 해결하였다.

양수는 arr에 집어넣었고 음수는 arr2에 집어넣었다.

 

이런 문제는 가벼운 마음으로 접근하면 안 될거 같다. 조건이 생각보다 많다.