[백준 1092] 배(C++)

📕문제

---

 

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

📕입력

---

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

📕출력

---

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

 

🔎문제 해석

---

이 문제는 최소한의 시간 즉 최대 효율로 박스를 옮겨야 하는 알고리즘입니다.

전형적인 그리디 알고리즘이고 여기서 문제의 쟁점은

내림차순으로 정렬해서 진행하느냐, 오름차순으로 정렬해서 진행하느냐에 있습니다.

효율적으로 크레인이 일하기 위해서는 무거운 상자를 무게 제한이 높은 크레인에 할당해주고, 가벼운 무게의 상자는 가벼운 무게의 크레인에 할당해주는 것이 맞습니다.

그리고 가장 무거운 무게가 가장 무거운 크레인에 들어가지 못한다면

배로 박스를 모두 옮길 수 없기 때문에[검사의 용이성] 크레인과 박스의 무게는 내림차순으로 정렬하는것이 적절합니다.

 

모든 박스와 크레인을 내림차순으로 정렬한 뒤
가장 무거운 박스와 크레인을 비교 -> 만약 박스가 더 무겁다면 -1을 출력하고 종료
크레인이 무겁다면 이제 배로 모두 옮길수 있다는 뜻이므로 다음 단계를 진행한다. 
크레인의 개수대로 박스를 검사하고, 크레인의 무게와 박스를 하나하나 비교하면서 크레인에 담을 수 있다면 박스를 담고, 박스를 제거한 뒤, 다음 크레인으로 넘어가면 된다. 그리고 모든 크레인을 다 사용했을 때 1분을 계속 더해주면 된다.

💻코드

/*
백준 골드5 배
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n, m;
int t = 0;
vector<int> crain;
vector<int> box;
bool comp(int a, int b)
{
    return a > b;
}
int main()
{
    cin >> n;
    crain.resize(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> crain[i]; 
    }
    sort(crain.begin(), crain.end(), comp); //내림차순
    cin >> m;
    box.resize(m, 0);
    for (int i = 0; i < m; i++)
    {
        cin >> box[i];
    }
    sort(box.begin(), box.end(), comp); //내림차순
    if (box[0] > crain[0])
    {
        cout << -1;
    }
    else
    {
        while (box.size() != 0)
        {
            t++;
            for (int i = 0; i < n; i++)
            { //포크레인으로 돌리고
                for (int j = 0; j < box.size(); j++)
                {
                    if (crain[i] >= box[j])
                    {
                        box.erase(box.begin() + j);
                        break;
                    }
                }
            }
        }
        cout << t;
    }
}

 

✔느낀 점

• 그리디는 최선의 결과를 내야 하는 알고리즘을 짜야 하기에 첫 단추가 중요하다.
• 회의실 배정과 계단 문제 등과 같은 문제는 문제를 잘 파악해서 오름차순, 내림차순 중 어느 걸로 정렬해야 하는지가 중요하다