BOJ - 배(1092)

골드2 : 그리디, 정렬 문제이다.

생각

실제로 운송물을 움직인다고 생각해보자. 그렇다면 가장 무거운 하중을 움직일 수 있는 크레인이 가장 많이 움직여야 최단 시간에 짐을 움직일 수 있다. 이부분이 핵심이다. 그리고 짐을 움직일 수 없는 경우는, 가장 무거운 하중을 움직일 수 있는 크레인이 가장 무거운 하중을 못옮길 때이다.

알고리즘

1. 가장 무거운 하중을 옮길 수 있는 순서로 정렬한다.
2. 하중도 무거운 하중부터 정렬한다.
3. 가장 무거운 하중을 옮길 수 있는 크레인이 가장 무거운 하중을 옮길 수 있는지 확인한다.
4. 옮길 수 없다면 -1을 출력한다.
5. 옮길 수 있다면 가장 무거운 하중을 옮기는 크레인 부터 무거운 하중 부터 옮긴다.
6. 이 과정을 모든 하중을 옮길 때까지 반복하고 그 때까지 걸리는 시간을 출력한다.

Code

#include <iostream>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <vector>
using namespace std;
int N, M;
int crane[51];
vector<int> box;
 
int main(){
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> crane[i];
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        int temp;
        cin >> temp;
        box.push_back(temp);
    }
    sort(crane, crane+N, greater<>());
    sort(box.begin(), box.end(), greater<>());
 
    if (box[0] > crane[0]) {
        cout << -1 << '\n';
        return 0;
    }
 
    int loaded = 0, index = 0, count = 0;
    while (loaded != int(box.size())) {
        for (int i = 0; i < M; i++) {
            if (crane[index] >= box[i] && box[i] != 0) {
                box[i] = 0;
                loaded++;
                index++;
            }
            if (index == N) break;
        }
        count++;
        index = 0;
    }
 
    cout  <<  count << '\n';
 
    return 0;;
 
}
 

Reference

• 백준(1092번) - 배