[백준]Baekjoon1744(Greedy Algorithm)

문제링크 : https://www.acmicpc.net/problem/1744

쉬운듯 보이나 의외로 까다로웠던 문제이다.

기본적으로는 음수와 양수별로 나누어 음수는 가장 작은수부터 2개씩 , 양수는 가장 큰 수부터

2개씩 짝을지어 곱해서 더해주면 된다.

그러니까 예를들어 -5 -1 4 2 3 -3 이 있다고 하면

음수는 -5 -3 -1 과 같이 오름차순으로 정렬하여 2개씩 짝지어 곱한 후 더해주고

양수는 4 3 2 와 같이 내림차순으로 정렬하여 2새씩 짝지어 곱한 후 더해주는 식이다.

놓치기 쉬운 부분은 1같은 경우 짝지어 곱해주는 것보다 따로 더해주는게 

값을 더 크게한다는 사실이다. 

고로 1이 나오는 경우 음수배열에 추가시키지 말고 결과값에 바로 1을 더하도록 한다.

마지막으로 2개씩 짝지어 더하는 과정에서 편하게 반복문을 수행하기 위해

배열을 짝수값으로 맞춰주었다.

만약 음수배열의 길이가 홀수라면 음수중 가장 큰 값을 미리 결과값에 연산해 준 후 

vector배열에서 그 값을 제거해주었고

양수배열같은 경우 길이가 홀수라면 1을 곱하면 어차피 같으므로 1을 배열에 추가해주었다.

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

using namespace std;
bool cmp(int x, int y) {
	if (x > y) return true;
	else return false;
}
int main()
{
	vector<int> plus;
	vector<int> minus;

	int N;
	scanf("%d", &N);
	int num;
	int result = 0;
	while (N--) {
		scanf("%d", &num);
		if (num == 1) result += 1;
		else {
			num > 0 ? plus.push_back(num) : minus.push_back(num);
		}
	} 
	sort(minus.begin(), minus.end());
	sort(plus.begin(), plus.end(),cmp);
	if (plus.size() % 2 == 1) plus.push_back(1);
	if (minus.size() % 2 == 1) {
		result += minus.back();
		minus.pop_back();
	}

	for (int i = 0; i < minus.size(); i+=2) {
			result += minus[i] * minus[i + 1];
	}
	for (int i = 0; i < plus.size(); i += 2) {
			result += plus[i] * plus[i + 1];
	}
	printf("%d\n", result);
}