[백준/BOJ] 백준 1092번 : 배

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

1092번: 배

무게 제한이 가장 큰 크레인부터 옮길 수 있는 박스 중 가장 무거운 박스를 옮긴다. 가장 무거운 걸 옮길 수 있는 크레인이 가장 무거운 박스를 옮기지 못할 때는 박스를 옮길 수 있는 방법이 없는 것이다. 해당 시간에 더 이상 박스를 옮길 수 없으면 다음 시간으로 넘어간다(cnt++)

 

코드

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

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

	int n,m;
	vector <int> crane;
	multiset <int> box;
	multiset <int>::iterator it;
	int temp;
	int cnt = 0;
	bool finish = false;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		crane.push_back(temp);
	}

	//크레인을 내림차순으로 정렬한다
	sort(crane.begin(), crane.end());
	reverse(crane.begin(), crane.end());

	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> temp;

		//box를 이진트리를 통해 저장한다
		box.insert(temp);
	}

	//가장 무거운걸 옮길 수 있는 크레인이 가장 무거운 박스를 옮기지 못할때
	if (crane[0] < *box.rbegin())
	{
		cout << -1;
		return 0;
	}

	while (!finish)
	{
		//더이상 옮길 박스가 없을때
		if (box.empty())
		{
			break;
		}

		cnt++;//크레인들이 움직인다(시간 증가)

		//무게제한이 가장 큰 크레인부터 옮길 수 있는 박스중 가장 무거운 박스를 옮긴다
		for (int i = 0; i < n; i++)
		{
			//더이상 옮길 박스가 없을때
			if (box.empty())
			{
				finish = true;
				break;
			}

			else
			{
				//크레인이 옮길 수 있는 박스중 가장 무거운 박스를 옮긴다
				//옮긴 박스는 지운다

				//crane[i]이상의 박스 중 가장 가벼운 박스를 고른다
				it = box.lower_bound(crane[i]);

				//옮길 수 있는 박스가 없을때 해당 시간에서는 더 이상 박스를 옮길 수 있는게 없다
				if (it == box.begin() && *it > crane[i])
				{
					break;
				}

				//crane[i]이 모든 박스를 옮길 수 있을때(it == box.end() 일때) 가장 무거운 박스를 옮길 수 있고
				//또는 (*it > crane[i])이면 it위치의 박스는 옮길 수 없지만 (--it)위치의 박스는 옮길 수 있다  
				else if (it == box.end() || *it > crane[i])
					box.erase(box.lower_bound(*(--it)));

				//박스중 정확이 crane[i]의 무게 제한과 같은 무게의 박스가 있을때 해당 박스를 옮긴다
				else if (*it == crane[i])
					box.erase(box.lower_bound(crane[i]));
			}
		}
	}

	cout << cnt;
	
	return 0;
}