[백준] 1744. 수 묶기

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

1744번: 수 묶기

---

🙄 생각 과정 🙄

​

1. 입력 받은 일련의 수를 양수/ 음수/ 0으로 구분

​

2. 양수 - 수가 짝수 개 있을 때 : 둘씩 곱하여 더한다.

- 수가 홀수 개 있을 때 : 가장 작은 수 다음부터 둘씩 곱하여 더한다

(단, 둘 중 하나라도 1일 경우 그냥 더해야 한다.)

​

3. 음수 - 수가 짝수 개 있을 때 : 둘씩 곱하여 더한다.

- 수가 홀수 개 있을 때 : 가장 큰 수 다음부터 둘씩 곱하여 더한다

- 0이 존재할 경우 : 가장 큰 수와 0을 곱하여 더한다.

- 0이 존재하지 않을 경우 : 가장 큰 수를 더한다.

​

실패한 경우

why : 양수의 경우 묶인 2개의 수 중 하나가 1이면 더해야 한다는 것을 간과함

 

// 실전압축성장 (그리디 알고리즘 편)
// 수 묶기

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

int main() {

	int N;
	cin >> N;

	vector<long long int> Plus;
	vector<long long int> Minus;
	bool zero = false;

	for (int i = 0; i < N; i++) {

		long long int x;
		cin >> x;

		if (x > 0) Plus.push_back(x);
		if (x < 0) Minus.push_back(x);
		if (x == 0) zero = true;
	}

	sort(Plus.begin(), Plus.end());
	sort(Minus.begin(), Minus.end());
	int plus_size = Plus.size();
	int minus_size = Minus.size();

	long long int result = 0;

	if (Plus.size() > 0) {

		if (Plus.size() % 2 == 0) {

			for (int i = 0; i < plus_size - 1; i += 2) {
				
				if ((Plus[i] == 1 && Plus[i + 1] == 1) || (Plus[i] == 1 && Plus[i + 1] == 2)) {
					result += Plus[i] + Plus[i + 1];
				}

				else 
					result += Plus[i] * Plus[i + 1];
			}
		}

		else {

			if (Plus.size() > 1) {

				for (int i = 1; i < plus_size - 1; i += 2) {

					if ((Plus[i] == 1 && Plus[i + 1] == 1) || (Plus[i] == 1 && Plus[i + 1] == 2)) {
						result += Plus[i] + Plus[i + 1];
					}

					else 
						result += Plus[i] * Plus[i + 1];
				}
			}

			result += Plus[0];
		}
	}

	if (Minus.size() > 0) {

		if (Minus.size() % 2 == 0) {

			for (int i = 0; i < minus_size - 1; i += 2) {

				result += Minus[i] * Minus[i + 1];
			}
		}

		else {

			if (Minus.size() > 1) {

				for (int i = 0; i < minus_size - 1; i += 2) {

					result += Minus[i] * Minus[i + 1];
				}
			}

			if (zero) {
				result += 0;
			}

			else {
				result += Minus.back();
			}
		}
	}
	cout << result;
}

// 이게 왜 안되는데

 

 

// 맞았습니다!

// 실전압축성장 (그리디 알고리즘 편)
// 수 묶기

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

int main() {

	int N;
	cin >> N;

	vector<long long int> Plus;
	vector<long long int> Minus;
	bool zero = false;

	for (int i = 0; i < N; i++) {

		long long int x;
		cin >> x;

		if (x > 0) Plus.push_back(x);
		else if (x < 0) Minus.push_back(x);
		else if (x == 0) zero = true;
	}

	sort(Plus.begin(), Plus.end());
	sort(Minus.begin(), Minus.end());
	int plus_size = Plus.size();
	int minus_size = Minus.size();

	long long int result = 0;

	if (Plus.size() > 0) {

		if (Plus.size() % 2 == 0) {

			for (int i = 0; i < plus_size - 1; i += 2) {
				
				if (Plus[i] == 1 || Plus[i + 1] == 1) {
					result += Plus[i] + Plus[i + 1];
				}

				else 
					result += Plus[i] * Plus[i + 1];
			}
		}

		else {

			if (Plus.size() > 1) {

				for (int i = 1; i < plus_size - 1; i += 2) {

					if (Plus[i] == 1 || Plus[i + 1] == 1) {
						result += Plus[i] + Plus[i + 1];
					}

					else 
						result += Plus[i] * Plus[i + 1];
				}
			}

			result += Plus[0];
		}
	}

	if (Minus.size() > 0) {

		if (Minus.size() % 2 == 0) {

			for (int i = 0; i < minus_size - 1; i += 2) {

				result += Minus[i] * Minus[i + 1];
			}
		}

		else {

			if (Minus.size() > 1) {

				for (int i = 0; i < minus_size - 1; i += 2) {

					result += Minus[i] * Minus[i + 1];
				}
			}

			if (zero) {
				result += 0;
			}

			else if (!zero) {
				result += Minus.back();
			}
		}
	}
	cout << result;
}