백준 Gold 5 배

배 (백준 Gold 5)

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

크레인이 들 수 있는 무게들 N개와
상자의 무게들이 M개 주어진다

크레인들이 상자를 동시에 옮긴다고 하였을 때
모든 상자들을 옮기는 데 걸리는 최소 시간

풀이 방법

높은 것을 들 수 있는 크레인이
높은 것을 드는것이 가장 좋은 상황이므로

크레인들은 '들 수 있는 가장 무거운 것' 부터 들어야 함

• 그렇기에 정렬을 통하여
  ‘각 크레인’이 들 수 있는 가장 무거운 박스의 ‘인덱스’를
  각각 지정
  

• 이후 반복을 통해
  크레인들이 ‘박스’를 차례대로 옮기도록 코드를 짰다
  (idxs 와 movedBox 배열)
  

제출 코드

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

using namespace std;

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

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

	int m;
	cin >> m;
	vector<int> boxs(m);
	for (int i = 0; i < m; i++)
		cin >> boxs[i];

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

	if (boxs.back() > crains.back())
	{
		cout << -1;
		return 0;
	}

	vector<int> idxs(n);
	vector<bool> movedBox(m,false);

	int idx = 0;
	for (int i = 0; i < m; i++)
	{
		while(boxs[i] > crains[idx])
		{
			idxs[idx] = i - 1;
			idx++;
		}
	}

	if (idx < n)
	{
		for (int i = idx; i < n; i++)
		{
			idxs[i] = m - 1;
		}
	}

	idxs.back() = m - 1;

	// 무게 무거운 녀석들부터 옮긴다
	int answer = 0;

	while (true)
	{
		bool allComplete = true;

		for (int i = 0; i < n; i++)
		{
			if (idxs[i] == -1)
				continue;

			bool cantMove = false;

			while (movedBox[idxs[i]])
			{
				idxs[i]--;
				if (idxs[i] < 0)
				{
					cantMove = true;
					break;
				}
			}

			if (cantMove)
				continue;

			movedBox[idxs[i]] = true;
			allComplete = false;
		}

		if (allComplete)
			break;

		answer++;
	}

	cout << answer;

	return 0;
}

결과

정렬을 통해 비교적 쉽게 접근할 수 있었던
문제였던 것 같다