백준 1744

백준 1744

이 문제는 수열이 주어졌을 때, 숫자들의 합의 최대값을 구하는 문제이다. 이 때, 수열에서 숫자 2개를 묶어서 곱할 수가 있다. 각 숫자는 한번만 묶을 수 있다.

숫자 두개를 묶어 곱할 때, 무조건 양수가 나와야 한다. 그리고 큰 숫자끼리 곱해야 최대값이 나오게 된다.
따라서 (음수 x 음수), (양수 x 양수)가 나와야 한다. (음수 x 양수)가 나와서는 안된다.
이때 주의해야할 점이 있는데, 0,1에서는 예외처리를 해주어야 한다.
음수와 0이 만나면 곱을 해서 0을 만들어야 하고, 양수와 0이 만나면 더해서 양수만 나오게 해야한다. 또 음수,양수가 1이 만나면 더하는 것이 값을 늘릴 수 있다.

for문 한번만 돌면서 0번 인덱스부터 확인하기 위해서, 처음에 입력 받을 때 1과 같거나 작은 경우 따로 모아서 오름차순으로 정렬하고 1보다 큰 경우 내림차순으로 정렬해서 하나의 vector로 모은다. 하나에 그냥 모아놓고 오름차순으로 정렬을 할 경우,
예를 들어 -2 0 4 5 7 라는 수열이 주어졌을 때, 앞의 인덱스부터 확인하면 (-20)+(45)+7 = 27 이라는 값이 나온다. 실제로는 (-20)+(75)+4 = 39 라는 값이 최대값이다.

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> v1, v2;
int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;

		if (a > 1) {
			v2.push_back(a);
		}
		else {
			v1.push_back(a);
		}
	}

	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end(), greater<>());



	if (v2.size() > 0) {
		for (int i = 0; i<v2.size(); i++) {
			v1.push_back(v2[i]);
		}
	}

	int t = v1[0]; int ans = 0; int k;
	if (n == 1) ans += t;
	else {
		for (int i = 0; i < v1.size(); i++) {
			if (i + 1 < n) {
				k = v1[i + 1];
			}
			else {
				k = 1;
			}
			if ((t != 1 && k != 1 && t != 0 && k != 0) && t*k>0) //(음수 * 음수) , (양수 * 양수)  {

				if (t * k > 0) {
					ans += t * k;
					i++;
					if (i + 1 >= n) break;
					t = v1[i + 1];
				}

			}
			else if (t < 0 && k == 0) { // (음수 * 0)
				i++;
				if (i + 1 >= n) break;
				t = v1[i + 1];
			}
			else  // (음수 + 양수) , (양수 + 1) , (음,양수 + 1)
				ans += t;
				if (i + 1 >= n) break;
				t = v1[i + 1];
			}
		}
	}
	cout << ans;

}