[백준][C++]1744번 수 묶기

문제

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

 

 

풀이

• 가능한 한 큰 수들끼리 묶어야 결괏값이 커진다.
• 음수끼리 곱하면 양수로 변한다.

 

그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘

 

 

코드

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

using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;
  
  vector<int> plus;
  vector<int> minus;
  int zero = 0;
 
  int num;
  for(int i = 0; i < N; i++)
  {
    cin >> num;
    
    if(num == 0)
    {
      zero++;
    }
    else if(num > 0)
    {
      plus.push_back(num);
    }
    else
    {
      minus.push_back(-num);
    }
  }

  sort(plus.begin(), plus.end());
  sort(minus.begin(), minus.end());

  int result = 0;
  
  int start_index = 0;
  if(plus.size() % 2 == 1)
  {
    result += plus[0];
    start_index = 1;
  }
  for(int i = plus.size() - 1; i >= start_index; i = i - 2)
  {
    result = result + max((plus[i] * plus[i - 1]), plus[i] + plus[i - 1]);
  }

  if(minus.size() % 2 == 1)
  {
    if(zero <= 0)
    {
      result -= minus[0];
      start_index = 1;      
    }
  }
  for(int i = minus.size() - 1; i >= start_index; i = i - 2)
  {
    result += (minus[i] * minus[i - 1]);
  }

  cout << result;

  return 0;
}