[1092] 배(C++)

문제

바로가기

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

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

 

 

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다.

둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다.

셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다.

넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

 

 

출력

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

 

 

알고리즘

• 그리디 알고리즘
• 이분 탐색

 

 

해결 방법

그리디와 이분 탐색을 사용하여 해결할 수 있는 문제.

이분 탐색을 위해 정렬된 배열이 필요하기 때문에 우선 크레인의 무게 제한과 박스의 무게를 각각 오름차순 정렬해준다.

문제에서 모든 박스를 배로 옮길 수 없는 경우에는 -1을 출력하라고 되어있는데, 그냥 박스의 최대 무게보다 크레인의 최대 무게 제한이 작다면 -1을 출력하고 프로그램이 종료되도록 예외처리해주면 된다.

그게 아니라면 매 분마다 크레인에 박스를 실으면 되는데, 무게 제한이 큰 크레인부터 작은 크레인까지 무거운 상자 순서대로 적재하기만 하면 된다.

 

예를 들어, 크레인이 3대가 있고 각각 최대 5, 6, 10의 무게 제한이 있다고 하자.

그리고 10개의 상자가 있고 무게는 각각 [6, 6, 6, 6, 6, 8, 8, 8, 9, 9, 9]라고 하자.

무거운 상자부터 무게 제한이 큰 크레인에 적재하면 되므로 무게 9의 상자를 무게 제한이 10인 크레인에 적재한다.

하지만 무게 제한이 5, 6인 크레인은 무게가 9인 상자를 적재할 수 없다. 그럼 어떻게 해야 될까?

우리는 최소 시간을 사용해서 박스를 전부 배에 실어야 하므로 최대한 많은 크레인을 사용해야 한다.

이때 이분 탐색을 사용하여 무게 제한이 5, 6인 크레인에 더 이상 적재할 수 있는 상자가 없는지 찾고, 있다면 적재해야 한다.

이렇게 모든 상자가 배에 실릴때까지 반복하고 시간을 출력하면 끝!

 

 

내 코드

// [1092] 배
// 이분 탐색, 그리디
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> crain, box;

void input()
{
    int num;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> num;
        crain.push_back(num);
    }
    cin >> m;
    for(int i = 0; i < m; i++) {
        cin >> num;
        box.push_back(num);
    }
}

void solve()
{
    int idx = 0, time = 0, transported = 0;
    sort(crain.begin(), crain.end());
    sort(box.begin(), box.end());

    if(box[m-1] > crain[n-1]) {
        cout << "-1\n";
        return;
    }
    while(transported < m) {
        for(int limit: crain) {
            int idx = upper_bound(box.begin(), box.end(), limit) - box.begin();
            if(idx > 0) {
                box.erase(box.begin() + idx - 1);
                transported++;
            }
        }
        time++;
    }
    cout << time << '\n';
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    solve();

    return 0;
}