#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에 집어넣었다.
이런 문제는 가벼운 마음으로 접근하면 안 될거 같다. 조건이 생각보다 많다.
'백준 > 그리디' 카테고리의 다른 글
[백준] C++ 1041번(주사위) (0) | 2024.07.03 |
---|---|
[백준] C++ 12904번(A와 B) (0) | 2024.07.02 |
[백준]C++ 11000(강의실 배정) (0) | 2024.06.29 |
[백준] C++ 1715(카드 정렬하기) (0) | 2024.06.28 |
C++ 1026번(보물) (0) | 2024.06.27 |