[백준] 1092-배(C++)

문제링크:https://www.acmicpc.net/problem/1092

1092번: 배

 

그리디 문제입니다.

항상 최선의 선택을 할 때 결과값이 도출되기 때문입니다.

 

해당 문제는 n 배열과 m 배열을 내림차순으로 정렬하고 순서대로 큰 짐을 먼저 옮겨주면 되는 문제였습니다.

 

못 옮기는 기준은 가장 센 크레인 (arr_n[0])이 가장 무거운 짐(arr_m[0]) 보다 작을 때 입니다.

 

 

그리고 일반 배열에 O(n*m)로 구현하시면 시간초과입니다. 

최악의 상황에 O(m*n*m) 이 되어 500,000,000로 5초가 걸리기 때문입니다.

 

 

정답코드입니다.

 

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

int arr_n[51] = { 0 };
vector <int> arr_m;
int n = 0, m = 0, result = 0;

bool cmp(int a, int b) {
	if (a > b)return true;
	return false;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr_n[i];
	cin >> m;
	int num = 0;
	for (int i = 0; i < m; i++) {
		cin >> num;
		arr_m.push_back(num);
	}

	sort(arr_n, arr_n + n, cmp);
	sort(arr_m.begin(), arr_m.end(), cmp);

	if (arr_n[0] < arr_m[0]) {
		cout << -1 << endl;
		return 0;
	}

	
	while (1) {
		result++;

		for (int i = 0; i < n; i++) {
			
			for (int j = 0; j < arr_m.size(); j++) {
				if (arr_n[i] >= arr_m[j]) {
					arr_m.erase(arr_m.begin() + j);
					break;
				}
			}
		}
	
		if (arr_m.size() == 0)
			break;
		
	}
	cout << result << '\n';

}

저는 벡터를 사용해서 짐을 뺄때마다 erase로 값을 지워주도록 구현하였습니다.