백준 1092 배

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

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


using namespace std;

vector<int> lim;
vector<int> box;


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    int ans = 0;

    cin >> n;

    lim.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> lim[i];
    }

    sort(lim.begin(), lim.end(), greater<int>());

    cin >> m;

    box.resize(m);

    for (int i = 0; i < m; i++) {
        cin >> box[i];
    }

    sort(box.begin(), box.end(), greater<int>());

    if (box.front() > lim.front()) {
        cout << -1;
        return 0;
    }

    while (!box.empty()) {
        ans++;

        for (int i = 0; i < lim.size(); i++) {
            for (int j = 0; j < box.size(); j++) {
                if (lim[i] >= box[j]) {
                    box.erase(box.begin() + j);
                    break;
                }
            }
        }
    }

    cout << ans;

    return 0;
}

1. 문제

 n개의 크레인의 무게 제한과 m개의 상자의 무게가 주어진다. n개의 크레인을 사용하여 m개의 상자를 배로 옮기려 한다. 한 개의 크레인은 하나의 상자를 옮길 수 있고, 그 때 걸리는 시간은 1이다. n개의 크레인을 동시에 운용할 수 있을 때, 모든 상자를 배로 옮기는 데 걸리는 최소 시간을 구하라.

2. 풀이

그리디 문제이다. 가장 무거운 상자를 가장 무게 제한이 높은 크레인으로 배로 옮기는 방식을 사용하여 해결할 수 있다.

sort(lim.begin(), lim.end(), greater<int>());
sort(box.begin(), box.end(), greater<int>());

우선 크레인과 상자 배열을 내림차순으로 정렬한다.

if (box.front() > lim.front()) {
    cout << -1;
    return 0;
}

 가장 무거운 상자가 크레인의 가장 높은 제한보다 더 무겁다면 모든 상자를 배로 옮길 수 없으므로 -1을 출력한다.

while (!box.empty()) {
    ans++;

    for (int i = 0; i < lim.size(); i++) {
        for (int j = 0; j < box.size(); j++) {
            if (lim[i] >= box[j]) {
                box.erase(box.begin() + j);
                break;
            }
        }
    }
}

각 크레인에 대해 상자를 옮길 수 있다면 해당 상자를 배열에서 지운다. 모든 크레인을 다 확인한 후 상자가 남아있다면 같은 연산을 계속 진행하여 상자를 차례로 배로 옮긴다. 옮길 때마다 시간 값인 ans를 더해준다. 이를 출력하면 정답을 구할 수 있다.