[백준] 1744번: 수 묶기

1744번: 수 묶기

 

 

이 문제는 그리디 문제는 맞지만 다른 그리디 문제보다는 신경 써주어야 할 조건들이 많습니다.

 

* 수들을 두 개씩 묶거나 묶지 않을 수 있다. (곱하지 않을 수 있다.)

* 적절히 묶은 수열의 합을 구했을 때 그 값의 최댓값을 구하는 것이 문제다.

 

여기서 절댓값이 큰 순서대로 곱해줄 경우, 합의 최댓값이 가장 큼을 알 수 있습니다.

-5, -4, 5, 6이 있다면, -5와 -4, 5와 6을 곱해주는 경우가 가장 큽니다.

또, 부호의 변경을 신경 써 주어야 합니다.

 

 

여기서 주의 깊게 보아야 할 포인트는 세 가지가 있습니다.

 

1. 각 수의 부호

2. 0 (어떤 수든 0을 곱해주면 0이 된다. 음수의 갯수가 짝수가 아니라면, 곱해서 양수로 변환 되지 못한 음수가 하나 남는데, 이 음수에 0을 곱해주면 0이 된다는 점을 이용합니다.)

3. 1 (1은 어떤 수를 곱해도 자기 자신을 반환하기 때문에, 1은 그냥 더해주는 것이 합의 최댓값을 구하는 데 도움이 됩니다.)

 

그리디로 문제를 풀어야 하므로 std::sort 를 이용하여 정렬을 한 후, 정렬된 수열을 이용하여 합의 최댓값을 구합니다.

 

 

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

int N;
vector<int> negative;
vector<int> positive;
int zero = 0;
int one = 0;

void input() {
  cin >> N;

  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    
    if (x < 0) {
      negative.push_back(x);
    }
    else if (x == 0) {
      zero++;
    }
    else if (x == 1) {
      one++;
    }
    else {
      positive.push_back(x);
    }
  }
}

void sortSequence() {
  sort(negative.begin(), negative.end());
  sort(positive.begin(), positive.end());
}

long long calculateNegative() {
  long long ans = 0;
  int size = negative.size();

  for (int i = 0; i < size; i += 2) {
    if (i + 1 == size) {
      if (zero == 0) {
        ans += negative[i];
        break;
      }
    }
    ans += negative[i] * negative[i + 1];
  }
  return ans;
}

long long calculatePositive() {
  long long ans = 0;
  int size = positive.size();

  for (int i = size - 1; i >= 0; i -= 2) {
    if (i - 1 < 0) {
      ans += positive[i];
      break;
    }
    ans += positive[i] * positive[i - 1];
  }
  return ans;
}

long long calculateSum() {
  long long ans = calculateNegative() + calculatePositive() + one;

  return ans;
}

void printAnswer(long long ans) {
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);

  input();
  sortSequence();
  long long ans = calculateSum();
  printAnswer(ans);

  return 0;
}