[1092] 배

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

1092번: 배

<문제>

그리디 : 무게 제한이 높은 순으로, 무거운 박스부터 옮긴다(정렬)

(가장 무게제한이 높은 크레인) < (가장 무거운 박스) 일때에만 -1을 출력하면 되고, 그밖에는 모두 해가 존재한다.

 

입력을 vector로 받고, bfs처럼 while(!v.empty())로 간단하게 구현할 수 있다.

 

<소스코드>

#include<bits/stdc++.h>
using namespace std;
int n, m;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    vector<int>a(n);
    int i, j;
    for (i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end(), greater<>());
 
    cin >> m;
    vector<int>b(m);
    for (i = 0; i < m; i++)
        cin >> b[i];
    sort(b.begin(), b.end(), greater<>());
 
    if (b[0] > a[0]) {
        cout << "-1";
        return 0;
    }
    int turn = 0;
    while (!b.empty()) {
        turn++;
        for (i = 0; i < a.size(); i++) {
            for (j = 0; j < b.size(); j++) {
                if (a[i] >= b[j]) {
                    b.erase(b.begin() + j);
                    break;
                }
            }
        }
    }
    cout << turn;
    return 0;
}