백준 Gold 4 수 묶기

수 묶기 (백준 Gold 4)

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

길이가 N인 수열이 주어지고
각각의 숫자들은 ‘한쌍’으로 묶여 ‘곱’해진 후 더해질 수 있다
그렇지 않으면 혼자로서 더해질 수 있다
(모든 수들은 한번만 묶거나, 묶지 않아야 한다)

N 번째 수열이 주어졌을때
수들을 적절히 묶어 그 합이 최대가 되게 하는 문제

첫 제출 코드

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

using namespace std;

bool check(const vector<int>& vec, int right, int left, int& sum)
{
	if (right < left)
		return true;

	if (left == right)
	{
		sum += vec[left];
		return true;
	}

	if (left == right - 1)
	{
		if ((vec[left] > 1 && vec[right] > 1) ||
			(vec[left] < 0 && vec[right] <= 0))
		{
			sum += (vec[left] * vec[right]);
		}
		else
		{
			sum += vec[left];
			sum += vec[right];
		}
		return true;
	}
	return false;
}

int main()
{
	int n;
	cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n; i++)
		cin >> vec[i];

	if (n == 1)
	{
		cout << vec[0];
		return 0;
	}

	sort(vec.begin(), vec.end());

	int sum = 0;

	int left = 0, right = n - 1;

	while (true)
	{
		if ((vec[right] > 1 && vec[right - 1] > 1) ||
			(vec[right] < 0 && vec[right - 1] <= 0))
		{
			sum += (vec[right] * vec[right - 1]);
			right -= 2;
		}
		else
		{
			sum += vec[right];
			right--;
		}

		if (check(vec, right, left, sum))
			break;

		if ((vec[left] > 1 && vec[left + 1] > 1) ||
			(vec[left] < 0 && vec[left + 1] <= 0))
		{
			sum += (vec[left] * vec[left + 1]);
			left += 2;
		}
		else
		{
			sum += vec[left];
			left++;
		}

		if (check(vec, right, left, sum))
			break;
	}

	cout << sum;

	return 0;
}

틀린 이유?

일단 정렬을 통해 그리디 문제가 될 수 있다고 생각하였다

그래서 정렬 이후, left와 right 를 사용한 투 포인터 방식을
통해 ‘각각’의 위치에 따라 곱해지면 될것이라 생각하였다

다만, ‘양수’와 ‘음수’에 따른 처리와
left와 right가 만나기 직전에 대한 처리가
무척 까다로워 졌으며
그에 따라 내부 테스트 케이스 등에서 오답처리가 발생하였다

풀이방법

다시금 생각을 해보았다

• ‘양수’는 곱하는 게 이득이지만
  양수 1은 그냥 더해야 함
  

• ‘음수’는 음수끼리 곱하는게 이득이지만
  0과 곱하여 0으로 만들 필요 또한 있음
  

그렇기에 양수(1 제외) / 음수 + 0 으로
공간을 구분시킬 필요가 있다고 판단하였다

일단 1이 들어오면 바로 sum에 더해주고
양수는 양수용 힙에
음수와 0은 음수용 힙에 집어 넣어주었다

양수 힙은 내림차순,
음수 힙은 오름차순으로 정렬하도록 설정

이후 각각의 top에서 수를 뽑아
empty()인지 확인하고 곱하거나 더함으로서
sum에 적용하여 문제 해결

요점은 ‘각각’의 공간을
정렬 시키는 것이라 생각한다
(지금 생각해보니 vector로 나누어 정렬하였어도
되었을것 같기도)

최종 제출 코드

#include<iostream>
#include<queue>

using namespace std;

int main()
{
	int n;
	cin >> n;
	int sum = 0;

	priority_queue<int, vector<int>> pH;
	priority_queue<int, vector<int>,greater<int>> mH;

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

		if (t == 1)
		{
			sum += t;
		}
		else if (t > 1)
		{
			pH.push(t);
		}
		else
		{
			mH.push(t);
		}
	}

	while (pH.empty() == false)
	{
		int p = pH.top();
		pH.pop();

		if (pH.empty() == false)
		{
			sum += (p * pH.top());
			pH.pop();
		}
		else
		{
			sum += p;
		}
	}

	while (mH.empty() == false)
	{
		int m = mH.top();
		mH.pop();

		if (mH.empty() == false)
		{
			sum += (m * mH.top());
			mH.pop();
		}
		else
		{
			sum += m;
		}
	}

	cout << sum;

	return 0;
}

결과

Priority_queue(힙)을 통해
비교적 잘 구현할 수 있었다