[백준 1744] 수 묶기

우선 양수만 생각해보자

 

주어진 양수로 가장 큰 수를 만들려면 가장 큰 놈 두 놈끼리 곱해준 걸 합친게 가장 큰 수이다.

 

a < b < c < d 라 했을때

a < a+n < a+m < a+l 이라 할 수 있고

이 4개의 수 중 두 개의 수로 만들 수 있는 최대값은

(a+m)*(a+l) 이다. 

모든 경우의 수에서 a*a 는 동일하게 나온다고 쳤을때 (m+l)*a + m*l 이 가장 큰 경우이기 때문.

 

따라서 내림차순으로 정렬하고 앞에서부터 2개씩 묶어주면된다

 

그럼 음수쪽을 보자

 

음수쪽은 음수*음수이면 양수이므로

가장 작은 음수 두 개끼리 곱해준걸 합친게 가장 큰 수이다.

 

여기서 만약 수가 남는 경우를 생각해봐야하는데

만약 음수 하나가 남으면 그건 어쩔 수 없이 더해주어야하는 상황인데

만약 0이 있으면 0이랑 곱해서 그냥 0을 만드는게 좋다

따라서 0도 음수 취급을 해주면 된다.

 

일단 이렇게 생각하고 제출했는데 틀이 떠서 보아하니

이런 경우는 예외로 해줘야한다

 

만약 양수 쪽에서 2 1 이나 1 1 이 남으면

2*1 < 2+1 , 1*1 < 1+1 이므로

이렇게 곱한 것보다 그냥 더해준 경우가 더 클때가 있다

 

따라서 비교해서 곱한게 더 크면 곱해주고

아니면 그냥 두 개를 더하는 방식으로 풀어주었다

조건문 하나를 더 추가했다

 

---

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

using namespace std;

int N;

// 양수 최대한 살리기
// 음수 최대한 양수 만들기
// 그래서 0은 음수배열쪽에
// 음수가 홀수개 남으면 남은 음수 곱해줘서 0으로 만들면 되니까

int solve(vector<int> v) {
	int n = v.size();
	int sum = 0;
	for (int i = 0; i < (n / 2) * 2; i += 2) {
		if (v[i] * v[i + 1] > v[i] + v[i + 1]) sum += v[i] * v[i + 1];
		else sum += v[i] + v[i + 1];
	}

	if (n % 2 == 0) return sum;
	else return sum + v.back();
}

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

	cin >> N;

	vector<int> posv, negv;
	int x;

	for (int i = 0; i < N; i++) {
		cin >> x;
		if (x > 0) posv.push_back(x);
		else if (x <= 0) negv.push_back(x);
	}

	// 내림차순 정렬
	sort(posv.begin(), posv.end(), greater<>());
	// 오름차순 정렬
	sort(negv.begin(), negv.end());

	cout << solve(posv) + solve(negv) << "\n";
	return 0;
}