[Algorithm Problem] 배 (BAEKJOON: 1092)

배 (BAEKJOON: 1092)

이 문제는 생각보다 발상이 쉽지 않았다. 힌트의 Greedy Algorithm을 보고서야 크레인이 현재 옮길 수 있는 상자 중 최고 무게를 옮기기를 떠올렸다. 그러나 시간초과의 벽에 막혀 질문과 다른 사람들의 풀이를 보았는데, 모두 vector의 erase() 메소드를 사용해 시간을 줄이고 있었다. 나는 라이브러리는 최소로 사용하고자 정렬과 원소 삭제를 직접 구현했다.

풀이

#include<iostream>

using namespace std;

int N, M, boat[60], box[10010];

void merge_sort(int* arr, int s, int e) {
	if (s == e) return;
	int m = (s + e) / 2;

	merge_sort(arr, s, m);
	merge_sort(arr, m + 1, e);

	int tmp[10010] = { 0, };
	int l = s, r = m + 1, k = s;

	while (l <= m && r <= e) tmp[k++] = arr[l] > arr[r] ? arr[l++] : arr[r++];
	while (l <= m) tmp[k++] = arr[l++];
	while (r <= e) tmp[k++] = arr[r++];
	for (int i = s; i <= e; i++) arr[i] = tmp[i];
}

void erase(int* arr, int idx, int length) {
	while (idx < length - 1) {
		arr[idx] = arr[idx + 1];
		idx += 1;
	}
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> boat[i];
	cin >> M;
	for (int i = 0; i < M; i++) cin >> box[i];

	merge_sort(boat, 0, N - 1);
	merge_sort(box, 0, M - 1);
	
	if (boat[0] < box[0]) {
		cout << -1;
		return 0;
	}

	int cnt = 0, iteration = 0, box_num = M;
	while (cnt < box_num) {
		for (int boat_idx = 0; boat_idx < N; boat_idx++) {
			for (int box_idx = 0; box_idx < M; box_idx++) {
				if (box[box_idx] <= boat[boat_idx]) {
					erase(box, box_idx, M);
					M -= 1;
					cnt += 1;
					break;
				}
			}
		}

		iteration += 1;
	}

	cout << iteration;
	return 0;
}