백준 1092번 배 C++

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

 

1. 크레인과 박스들을 내림차순으로 정렬한다.

2. 맨 앞의 박스가 크레인이 감당할 수 있는 무게보다 무거우면 옮길수 없으므로 1을 출력하고 프로그램을 종료한다.

3. 박스가 전부 빌 때까지 크레인을 순회하면서 박스를 순회하면서 (2중 for문) 박스를 담을 수 있으면 박스의 벡터에 erase를 통해 박스를 지워준다. (크레인 한 번 순회하면 cnt++)

 

위에처럼 풀어도 풀리긴 하지만 박스를 지우는 erase가 시간이 오래 걸린다. 크레인이 500개만 되어도 시간초과가 날 것이다.

 

그래서 erase를 사용하지 않고 visited를 이용해 이미 담은 것인지를 판별하도록 코드를 수정하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n, m;

bool compare(const int& lhs, const int& rhs) {
	return lhs > rhs;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	vector<int> cranes(n);
	for (int i = 0; i < n; i++) {
		cin >> cranes[i];
	}
	cin >> m;
	vector<int> boxes(m);
	vector<bool> visited(m, false);
	for (int i = 0; i < m; i++) {
		cin >> boxes[i];
	}
	sort(cranes.begin(), cranes.end(), compare);
	sort(boxes.begin(), boxes.end(), compare);
	if (cranes[0] < boxes[0]) {
		cout << -1;
		return 0;
	}
	int cnt = 0;
	int sum = 0;
	int idx = 0;
	while (idx < m) {
		cnt++;
		int tmp_idx = idx;
		bool isConnected = true;
		for (int i = 0; i < static_cast<int>(cranes.size());) {
			if (tmp_idx >= m) break;
			if (boxes[tmp_idx] <= cranes[i] && !visited[tmp_idx]) {
				visited[tmp_idx] = true;
				sum++;
				tmp_idx++;
				i++;
				if (isConnected) idx = tmp_idx;
			}
			else {
				if (isConnected) isConnected = false;
				tmp_idx++;
			}
		}
		if (sum == m) break;
	}
	cout << cnt;
};