[BOJ] 1744 : 수 묶기 - travelbeeee

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

---

그리디 Greedy

그리디 기법을 이용해서 문제를 해결할 수 있습니다.

● 입력을 양수와 음수, 0 으로 구분합니다.

● 양수는 큰 수부터 차례대로 2개씩 묶어서 곱해서 더해주면 됩니다. 이때, 2개씩 묶는데 1이 포함되어있다면 곱하는 것보다 그냥 더하는게 최대값이므로 따로 처리해줍니다.

● 음수는 절대값이 큰 수부터 차례대로 2개씩 묶어서 곱해서 더해주면 양수를 만들 수 있습니다.

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

using namespace std;

bool cmp(int a, int b) {
	if (a < b)
		return false;
	return true;
}

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

	int N, x;
	vector<int> plus, minus;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x;
		if (x > 0) plus.push_back(x);
		else minus.push_back(x);
	}
	sort(minus.begin(), minus.end(), cmp);
	sort(plus.begin(), plus.end());

	int ans = 0;
	while (!plus.empty()) {
		 if (plus.size() >= 2) {
			 if (plus[plus.size() - 1] == 1 || plus[plus.size() - 2] == 1)
				 ans += plus[plus.size() - 1] + plus[plus.size() - 2];
			 else
				 ans += plus[plus.size() - 1] * plus[plus.size() - 2];
			plus.pop_back();
		}
		else 
			ans += plus[plus.size() - 1];
		plus.pop_back();
	}
	while (!minus.empty()) {
		if (minus.size() >= 2) {
			ans += minus[minus.size() - 1] * minus[minus.size() - 2];
			minus.pop_back();
		}
		else
			ans += minus[minus.size() - 1];
		minus.pop_back();
	}
	cout << ans;
	return 0;
}

---