백준 1744- 수 묶기 c++

문제 이해부터 해보자

 

수열 {0,1,2,4,3,5}가 들어왔을때

두 수를 묶거나 묶지 않을 수 있다

그리고 묶는 것은 중복되지 않는다

무슨소리냐면

예를들어 (1,2)를 묶었는데 (2,4)로 또 2를 중복시켜 묶을 수는 없다는 것이다

 

묶게되면 묶은 두 수 끼리 곱해서 더해지고

묶지 않으면 그냥 더해진다

 

{0,1,2,4,3,5}의 이 규칙을 통해

최댓값을 내는 경우는

0,1, {2,3}, {4,5}이다

그러면 0+1+(2*3)+(4*5)가 되어

27이 된다

 

 

 

다음은 테스트케이스를 분석해보자

-1
2
1
3

이 경우는

-1,1,(2,3)을 해주면

-1 + 1 + (2*3) = 6이 최댓값

 

 

0
1
2
4
3
5

(5,4), (3,2) 1,0

20+6+1=27

 

 

-1

-1

 

 

 

-1
0
1

(-1,0), 1

0+1=1

 

 

1
1

1+1 = 2

 

 

다른 경우는 보통 큰 수 끼리 묶어서 곱하는데

그렇지 않은 경우가 예외적으로 있다

 

 

그래서 나는

음수를 받는 벡터 하나

양수를 받는 벡터 하나

0을 받는 벡터 하나

총 세개를 만들어서

정렬시키고

2개씩 묶어서 더해주다가

 

마지막으로 음수, 양수가 한개남았을때 예외적으로 처리해 주었다

 

예를들어

-6 0 6이 나오면

-6, (0,6) 보다

(-6,0) 6이 더 크다

음수와 0이 남은 경우는

묶어주면 0이돼서 더했을때 최댓값이 된다

 

 

그리고 

0 6이 남으면(0,양수)

묶어주지 않아야한다

 

-2,6이 남아도(음수, 양수)

묶어주지 않아야한다

 

이런식으로 

큰 수 부터 2개씩 차례로 묶어주다가

마지막으로 1개씩 남는 상황에서

일일히 처리를 해주었다

묶어줄지 더해줄지

 

 

나의 코드이다

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


#define MAX(a,b) a>b ? a : b

using namespace std;

bool cmp(int a, int b) {
	return a > b;
}

int main() {
	int n;
	long long int count = 0;
	cin >> n;
	vector<int> plus;
	vector<int> zero;
	vector<int> minus;

	


	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		if (temp == 0) {
			zero.push_back(temp);
		}
		else if (temp > 0) {
			plus.push_back(temp);
		}
		else {
			minus.push_back(temp);
		}
	}

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

	/*for (int i = 0; i < plus.size(); i++) {
		cout << "plus" << endl;
		cout << plus[i] << endl;
	}
	for (int i = 0; i < minus.size(); i++) {
		cout << "minus" << endl;
		cout << minus[i] << endl;
	}
	for (int i = 0; i < zero.size(); i++) {
		cout << "zero" << endl;
		cout << zero[i] << endl;
	}
	*/

	while (true) {
		if (plus.size() >= 2) {
			int prod, sum,max;
			sum = plus[0] + plus[1];
			prod = plus[0] * plus[1];
			max = MAX(sum, prod);
			count += max;
			plus.erase(plus.begin());
			plus.erase(plus.begin());
		}
		if (minus.size() >= 2) {
			int prod = minus[0] * minus[1];
			count += prod;
			minus.erase(minus.begin());
			minus.erase(minus.begin());
		}

		if (minus.empty() && plus.empty())
			break;
		
		if (plus.size() <= 1 && minus.size() <= 1) {
			bool plusfull = !plus.empty();
			bool minusfull = !minus.empty();
			bool zerofull = !zero.empty();

			//case1 plus o zero x minus x
			//case2 plus x zero x minus o	o가 하나인 경우
			//case3 plus x zero 0 minus x
			//case4 plus o zero o minus x   o가 두개인 경우
			//case5 plus o zero x minus o
			//caes6 plus x zero o minus o
			//case7 plus o zero o minus o	//o가 세개나 0개인경우
			//case8 plus x zero x minus x


			if (plusfull && !zerofull && !minusfull) {
				count += plus[0];
				plus.erase(plus.begin());
			}
			else if (!plusfull && !zerofull && minusfull) {
				count += minus[0];
				minus.erase(minus.begin());
			}
			else if (!plusfull && zerofull && !minusfull) {
				//
			}

			else if (plusfull && zerofull && !minusfull) {
				count += plus[0];
				plus.erase(plus.begin());
			}

			else if (plusfull && !zerofull && minusfull) {
				count += plus[0] + minus[0];
				plus.erase(plus.begin());
				minus.erase(minus.begin());
			}

			else if (!plusfull && zerofull && minusfull) {
				count += minus[0] * 0;
				minus.erase(minus.begin());
			}

			else if (plusfull && zerofull && minusfull) {
				count += (0 * minus[0]) + plus[0];
				plus.erase(plus.begin());
				minus.erase(minus.begin());
			}

			else if (!plusfull && !zerofull && !minusfull) {
				//
			}

		}

	}


	cout << count;

	return 0;
}

코드는 내가 생각해도 못짠거같은데

다른 아이디어가 떠오르지 않아서

근성으로 했다

 

 

 

아무튼 이 문제의 핵심은

2개씩 묶어주다가

1개가남으면

그 상황에서 어떻게 할것인가

양수와 0이남으면 더해주고

음수와 0이남으면 묶어주어야한다

양수와 음수가 남으면 더해주어야한다