이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 16 번째 글 입니다.
목차
골드2 : 그리디, 정렬 문제이다.
생각
실제로 운송물을 움직인다고 생각해보자. 그렇다면 가장 무거운 하중을 움직일 수 있는 크레인이 가장 많이 움직여야 최단 시간에 짐을 움직일 수 있다. 이부분이 핵심이다. 그리고 짐을 움직일 수 없는 경우는, 가장 무거운 하중을 움직일 수 있는 크레인이 가장 무거운 하중을 못옮길 때이다.
알고리즘
- 가장 무거운 하중을 옮길 수 있는 순서로 정렬한다.
- 하중도 무거운 하중부터 정렬한다.
- 가장 무거운 하중을 옮길 수 있는 크레인이 가장 무거운 하중을 옮길 수 있는지 확인한다.
- 옮길 수 없다면 -1을 출력한다.
- 옮길 수 있다면 가장 무거운 하중을 옮기는 크레인 부터 무거운 하중 부터 옮긴다.
- 이 과정을 모든 하중을 옮길 때까지 반복하고 그 때까지 걸리는 시간을 출력한다.
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;;
}