[BOJ] 1092번_배_그리디 (C++)

[문제]

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

무게 제한이 존재하는 크레인 N개가 존재할 때, 화물상자 M개를 배에 싣는 데 걸리는 시간을 구하는 문제이다. 크레인은 1분에 화물상자 1개씩 싣을 수 있으며, 크레인의 무게 제한보다 무거운 화물상자는 옮길 수 없다. 만약 모든 박스를 배에 싣을 수 없으면 -1을 출력한다.

[사용 알고리즘]

그리디

[풀이 핵심]

• 무게 제한이 큰 크레인은 무거운 화물상자를 옮기는 그리디한 방법으로 해결할 수 있다. 이를 해결하기 위해 크레인의 무게 제한과 화물상자의 무게를 입력받아 내림차순으로 정렬하고 무거운 화물상자부터 순차적으로 배에 싣어 주며, 총 걸리는 시간을 계산하는 느낌으로 코드를 짜주면된다.
• 배에 화물상자를 싣기전에 제일 무거운 화물상자가 제일 높은 무게 제한을 가지고 있는 크레인으로 옮길 수 없다면 "만약 모든 박스를 배에 싣을 수 없으면 -1을 출력한다." 라는 조건에 충족하기 때문에 -1을 출력하고 프로그램을 종료한다.

[코드]

//boj1092번_배_그리디 알고리즘

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

using namespace std;

bool compare(int x, int y) {
	return x > y;
}

int main() {
	int N;
	cin >> N;

	vector<int> crane;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		crane.push_back(num);
	}

	sort(crane.begin(), crane.end(), compare);

	int M;
	cin >> M;

	vector<int> box;

	for (int i = 0; i < M; i++) {
		int num;
		cin >> num;
		box.push_back(num);
	}

	sort(box.begin(), box.end(), compare);

	if (crane[0] < box[0]) {
		cout << -1;
		return 0;
	}

	int result = 0;

	while (true) {
		if (box.empty()) {
			break;
		}
		else {
			result++;

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

	cout << result;

	return 0;
}