백준 1092번 - 배(c++)

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

 

6개월만에 다시 본 문제. 그러나 엄청나게 틀렸다.. 문제 접근법이 틀리진 않았으나 조금 더 디테일이 필요하다.

문제 유형은 그리디로 각 크레인에 가장 비슷한 무게를 달아줘야한다. 그래서 필연적으로 크레인과 박스 둘 다 정렬이 필요한데, 여기서 어떻게 크레인과 박스를 매치해줄 수 있는가? 

 

그리디 하게 생각하면 

 

1. 크레인 x번을 모든 박스와 매칭해보고 가장 맞는 것을 고른다.

2. 이것을 크레인의 개수만큼 반복한다.

 

먼저 시간복잡도를 고려해보자. 그렇다면 O(N * M) 의 시간이 소요되며 최악의 경우 O(N * M * M)의 시간이 걸린다. M = 10000, N = 50 이므로 M * M은 안된다. 그래서 처음엔 각 박스의 인덱스를 bool 배열을 만들어 완료 표시를 해주었는데 시간초과가 났다. 그래서 아에 배열에서 제거해버렸다. 이러면 M의 개수가 계속 줄어들어 M^2 보다는 작아진다.

 

두번째로 어떻게 매칭해줘야할지 고려해보자.

크레인 3 7 10

박스 2 5 5 6 6 7 8 9 9

 

경우를 생각해보자. 두 배열을 오름차 정렬하면 위와 같고 매칭을 해보면

2 5 5

5 6 

7 8

9

9

 

총 5분이 걸린다. 

 

내림차 정렬하면?

10 7 3

9 9 8 7 6 6 5 5 2

 

이고

 

9 7 2

9 6

8 6

5 5

 

총 4분이 걸린다.

 

즉, 오름차하고 비교해버리면 아주 큰 크레인이 상대적으로 작은 박스들과 매칭되기 때문에 하드하게 처음부터 큰놈들끼리 비교해야한다. Greedy는 언제나최적을 고려해야하니까.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> crain;
vector<int> box;

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

	crain = vector<int>(N);

	for(int i = 0; i < N; i++){
		cin >> crain[i];
	}

	cin >> M;
	box = vector<int>(M);

	for(int i = 0; i < M; i++){
		cin >> box[i];
	}
	int answer = 0;

	sort(crain.rbegin(), crain.rend());
	sort(box.rbegin(), box.rend());

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

	int compSize = 0;
	while(true){
		answer++;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < box.size(); j++){
				if(box[j] <= crain[i]){ // 운반 가능
					box.erase(box.begin() + j);
					break;
				}
			}
		}

		if(box.empty()) break;
	}

	cout << answer << '\n';
}