백준1092 배

작성일 | In

문제 링크

  • http://icpc.me/1092

사용 알고리즘

  • Set
  • Binary Search

풀이

이 문제와 거의 동일한 문제입니다.

잘 생각해보면, 무거운 화물을 들 수 있는 크레인은 무조건 무거운 화물을 들고 가는 것이 이득입니다. 이 점을 활용해 시간을 최소화시키는 전략을 세워봅시다.

먼저 무거운 화물을 들 수 있는 크레인이 앞에 오게 정렬을 해줍시다.
화물도 내림차순으로 정렬을 해줍시다.
각 크레인에 대해 남은 화물 중에서 들 수 있는 가장 무거운 화물을 먼저 옮겨주면 됩니다. 만약 들 수 있는 화물이 없다면 해당 크레인은 스킵합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

multiset<int> s;
int n;
int arr[111];
int mx = 0;

int main(){
	int n; cin >> n;
	for(int i=0; i<n; i++) cin >> arr[i];
	sort(arr, arr+n, [](int a, int b){
		return a > b;
	});
	int m; cin >> m;
	for(int i=0; i<m; i++){
		int t; cin >> t;
		s.insert(t); mx = max(mx, t);
	}

	if(mx > arr[0]){
		cout << -1; return 0;
	}

	int ans = 0;
	while(1){
		if(s.empty()) break;
		ans++;
		for(int i=n-1; i>=0; i--){
			if(s.empty()) break;
			auto it = s.find(arr[i]);
			if(it != s.end()){
				s.erase(it); continue;
			}
			it = s.lower_bound(arr[i]);
			if(it == s.begin())  continue;
			--it;
			s.erase(it);
		}
	}
	cout << ans;
}