[백준/BOJ] 백준 22988번 : 재활용 캠페인

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

22988번: 재활용 캠페인

중간에서 만나는 투 포인터를 사용해서 두 개의 용기로 용량을 꽉 차게 만들 수 있는지 확인하여, 만들 수 있으면 해당 두 개를 선택하여 꽉 찬 용기를 만든다. 선택되지 않는 남은 용기가 3개 이상이면 두 개를 합치면 무조건 x/2 이상이 되고, 이것을 나머지 한 개와 합치면 x이상을 만들 수 있으므로 3개를 이용하면 무조건 꽉 찬 용량을 하나 만들 수 있는 것을 이용하여 남은 용기를 이용해 꽉 찬 용기를 추가로 만들 수 있는 경우를 고려하여 문제를 해결했다.

 

코드

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

int n;
long long x;
vector<long long> c;
int result = 0;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> x;

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

		//하나 스스로도 x용량이 될때
		if (input == x)
		{
			result++;
			continue;
		}

		c.push_back(input);
	}

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

	//중간에서 만나는 투포인터 이용
	int left = 0;
	int right = c.size() - 1;
	int remain = c.size(); //고를 수 있는 용기의 개수
	long long sum = 0;

	while (1)
	{
		if (left >= right)
			break;

		sum = c[left] + c[right];

		//용량을 꽉 차게 만들 수 있을때
		if (sum + (x / 2) >= x)
		{
			result++;

			//이번 left와 right는 선택했으므로 다른것에서 찾기 위해 옮긴다
			left++;
			right--;

			remain -= 2; //2개를 골랐으므로 남은 용기가 2개 줄어든다
		}

		//right는 고를 수 있는 용량중 최대 인데 부족한것 이므로 left를 오른쪽으로 옮긴다
		else
		{
			left++;
		}
	}

	//남은 용기가 3개 이상일때
	//두개를 합치면 무조건 x/2이상이 되므로 이것과 나머지 한개를 합치면 x이상을 만들 수 있다
	//그러므로 3개로 무조건 새로운 한개를 만들 수 있다
	if (remain >= 3)
	{
		result += (remain / 3);
	}

	cout << result;

	return 0;
}