백준 알고리즘 1744번 - 수 묶기

그리디 알고리즘.

벡터를 두개 만들어서 한 쪽에는 음수만, 한 쪽에는 양수만 저장.

각각 정렬을 각각 해준다.

큰 수끼리 곱하면 그 곱도 최대가 됨을 이용한다.

음수 * 음수 = 양수, 양수* 음수 = 음수 임을 이용한다.

 

예외 1 )  

1의 경우, 아무와도 짝짓지 않는 것이 유리하다. ex) 2 *1 =2 , 2+1=3

예외 2)

0의 경우, 홀수의 갯수가 홀수일때 곱해주면 음수를 하나 없앨 수 있다.

 

소스코드

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> pluss;
vector<int> minuss;
int ans;

int main() 
{
	int num,a;
	cin>>num;
	//벡터 두개에 각각 음수, 양수를 넣어준다.
	for(int i=1;i<=num;i++)
	{
		cin>>a;
		if(a==1) ans+=1;
		else if(a>0) pluss.push_back(a);
		else minuss.push_back(a);
	}
	//각각 정렬하는 부분
	sort(pluss.begin(),pluss.end());
	reverse(pluss.begin(),pluss.end());
	sort(minuss.begin(),minuss.end());
	//양수의 갯수가 홀수이면 하나남은 건 그냥 더해준다
	if(minuss.size()%2==1){
		ans+=minuss[minuss.size()-1];
		minuss.pop_back();
	}
	//양수의 갯수가 홀수라면 답에 그냥 더해준다. 
	if(pluss.size()%2==1){
		ans+=pluss[pluss.size()-1];
		pluss.pop_back();
	}
	//큰 것끼리 짝지어준다.
	for(int i=0;i<pluss.size();i+=2){
		ans+=pluss[i]*pluss[i+1];
	}
	//음수는 작은 것끼리 짝지어준다
	for(int i=0;i<minuss.size();i+=2){
		ans+=minuss[i]*minuss[i+1];
	}
	printf("%d",ans);
}