[백준 1092] 배

작성일 | In |

문제 링크

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

풀이

크레인의 무게 제한의 최댓값이 박스의 무게의 최댓값보다 크가나 같으면 박스를 언젠가는 배로 모두 옮길 수 있습니다. 반대의 경우에만 -1을 출력해주면 되고 다른 경우에는 답을 구하면 됩니다.

무게제한이 상대적으로 적은 크레인이 옮길 수 있는 화물은 상대적으로 큰 크레인의 화물에 포함되기 때문에 무게 제한이 큰 크레인만이 옮길 수 있는 화물을 처리하고 포함관계에 있는 화물을 같이 처리하는 것이 시간상으로 이득이 됩니다. 이는 크레인마다 집을 수 있는 가장 무거운 화물을 가져는 것으로 구현할 수 있습니다. 화물을 multiset으로 관리하고 크레인이 집을 수 있는 최대 무게의 화물을 upperbound로 찾고 지우는 것을 multiset이 빌때까지 반복하면 됩니다. 최악의 경우로 하나의 크레인만 일하고 나머지 크레인은 쉰다고 했을 때의 시간복잡도는 $O(NM \log M)$입니다. 무게 제한보다 큰 화물밖에 남지 않았을 때 그 크레인은 지우는 것으로 시간복잡도 $O(N \log N + M \log M)$으로 줄일 수는 있지만 굳이 할 필요는 없어보입니다.

전체 코드

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n, a[55], m;
multiset<int> s;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    cin >> m;
    for(int i=1;i<=m;i++){
        int a; cin >> a;
        s.insert(a);
    }
    if(*s.rbegin() > *max_element(a+1, a+1+n)) return cout << -1, 0;

    int ans = 0;
    while(!s.empty() && ++ans){
        for(int i=1;i<=n;i++){
            auto it = s.upper_bound(a[i]);
            if(it != s.begin()) s.erase(prev(it));
        }
    }
    cout << ans;
}