Backjoon_그리디_1744_수 묶기

직관적으로 상당히 쉬운 문제라 생각했는데 3번이나 틀렸다.

음수는 작은 값부터 정렬시키고(절댓값이 크기 때문에)
양수는 큰 값부터 정렬시킨다.

그리고 양수의 갯수=n,이고 음수의 갯수=m 이라 했을 때

n이 짝수라면)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-2] x v[n-1]
n이 홀수라면)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-3] x v[n-2] + v[n-1]

m이 짝수라면)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-2] x v[n-1]
n이 홀수라면)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-3] x v[n-2] + v[n-1]

여기서 1차 오류가 생겼다.
m이 홀수일 때 가장 작은 절댓값을 가진 v[n-1]은 음수기 때문에 더하면 손해이다.
만약 기존 수열에 0이 존재할 경우 음수를 더해주지 않아도 되므로
0이 있는지를 체크해야한다.

2차 오류는 고민해봐도 생각해낼 수가 없어서 인터넷에서 찾아봤다.
만약 1 1 1 1 이 입력될 경우
(1x1) + (1x1) 보다 1 + 1 + 1 + 1 이 더 크므로
1은 양수 수열을 골라낼 때 선택하지 않고 갯수만 체크해주고 마지막에 한번에 더해주기로 했다.

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

bool cmp(int a, int b) { return a > b; }
bool cmp1(int a, int b) { return a < b; }
int main()
{
	int n;
	int sum = 0;
	int zero_flag = 0; 
	int one_cnt = 0;

	vector<int> seq;
	vector<int> seq_pos;
	vector<int> seq_neg;

	cin >> n;
	while (n--)
	{
		int s;
		cin >> s;
		seq.push_back(s);
	}

	sort(seq.begin(), seq.end(),cmp);
	
	for (int i = 0; i < seq.size(); i++)
	{
		
		if (seq[i] > 1) seq_pos.push_back(seq[i]);
		else if (seq[i] < 0) seq_neg.push_back(seq[i]);
		else if (seq[i] == 0) zero_flag = 1; // 1차오류 
		else if (seq[i] == 1) one_cnt++; // 2차오류 
	}
	sort(seq_neg.begin(), seq_neg.end(), cmp1);
	
	
	if (seq_pos.size() % 2 == 0)
	{
		for (long unsigned int i = 0; i < seq_pos.size(); i = i + 2)
		{
			sum += (seq_pos[i] * seq_pos[i + 1]);
		}
	}
	else
	{
		for (long unsigned int i = 0; i < seq_pos.size()-1; i = i + 2)
		{
			sum += (seq_pos[i] * seq_pos[i + 1]);
		}
		sum += seq_pos[seq_pos.size() - 1];
	}

	if (seq_neg.size() % 2 == 0)
	{
		for (long unsigned int i = 0; i < seq_neg.size(); i = i + 2)
		{
			sum += (seq_neg[i] * seq_neg[i + 1]);
		}
	}
	else
	{
		for (long unsigned int i = 0; i < seq_neg.size() - 1; i = i + 2)
		{
			sum += (seq_neg[i] * seq_neg[i + 1]);
		}
		if (!zero_flag) { // 0이 없다면 
			sum += seq_neg[seq_neg.size() - 1];
		}
		
	}
	
	cout << sum+one_cnt;

	return 0;
}