백준 1092번 배( C++)

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

1092번: 배

 

정렬, 그리디 알고리즘 문제이다. 

난 그리디 알고리즘이 약한 것 같다.

 

- 내 접근법

먼저 Crain과 Weight는 최대한 비슷한 값 끼리 매져주는 것이 좋다. 그러므로 난 Crain은 오름차순, Weight는 내림차순 정렬을 해주었다.

그리고 Crain의 시작부분과 Weight의 시작부분부터 비교하며 크레인에 적재가 가능하면 Weight 벡터에서 삭제하고 다음 크레인의 상태로 넘어가는 식으로 문제를 해결했다. 

 

이 문제가 그리디인 이유는 처음 만났을 때 데리고 사라져 버리면 되기 때문이다. 뭔가 더 생각하거나 다시 돌아와 검증하지 않아도 된다.

 

먼저 논리를 새우고, 그것을 침착하게 구현하는 방법을 생각해보자 .

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> crain;
vector<int> weight;
int answer[10001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	queue<pair<int, int>> crainq;
	queue<int> weightq;
	
	int N, M;

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

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		weight.push_back(tmp);
	}
	sort(weight.rbegin(), weight.rend());
	sort(crain.rbegin(), crain.rend());

	if (weight[0] > crain[0]) {
		cout << "-1" << '\n';
		return 0;
	}

	vector<int> possibleCrain;
	for (int i = 0; i < N; i++) {
		if (crain[i] >= weight[M - 1]) {
			possibleCrain.push_back(crain[i]);
			answer[i] = 0;
		}
	}

	sort(possibleCrain.rbegin(), possibleCrain.rend());

	while (true) {
		for (int i = 0; i < crain.size(); i++) {
			for (int j = 0; j < weight.size(); j++) {
				if (crain[i] >= weight[j]) {
					answer[i]++;
					weight.erase(weight.begin() + j);
					break;
				}
			}
		}

		if (weight.empty())
			break;
	}

	int ans = -1;
	for (int i = 0; i < possibleCrain.size(); i++) {
		ans = max(answer[i], ans);
	}

	cout << ans << '\n';
}