*[백준][1092] 배

www.acmicpc.net/problem/1092

1092번: 배

문제

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

 

해결방법

1. 각 크레인의 최대 무게에 가장 가까운 무게 순으로 우선순위를 둔다면 최소한의 시간이 든다고 생각했다.

예를 들어 크레인의 무게는 4, 7, 9, 짐의 무게는 1, 1, 1, 9, 9 ,9가 있으면

(1, 1, 9), (1, 9), (9) 이와 같이 3 시간이 소요 된다.

 

2. 어떠한 방법으로 근사치의 값을 구 할 수 있을까 고민을 하다가, queue배열을 만들기로 결정했다.

queue배열을 만든 이유는 4, 7, 9의 크레인이 있다면, 0번 인덱스는 4에 매핑이 되며, 4보다 작거나 같은 무게들이 들어간다. 

queue[0] = {1, 1, 1}, queue[1] = {} , queue[2] = {9, 9, 9}와 같이 쌓이도록 했다. 이렇게 되면 매 시간마다 크레인이 들 수 있는 가장 가까운 값을 구 할 수 있게 된다.

 

3. 매 시간 각 크레인에서 들 수 있는 것을 체크하고 만약 현재 내 인덱스에 해당하는 Queue가 비어있다면, 나보다 작은 무게의 크레인에서 하나를 가져오면 된다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;

int main()
{
	int N, M, maxCrain = 0;
	bool possible = true;
	scanf("%d", &N);
	vector<int> crain;
	queue<int> waitList[50];
	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 0; i < N; i++) {
		int n;
		scanf("%d", &n);
		crain.push_back(n);
		if (maxCrain < n) {
			maxCrain = n;
		}
	}
	sort(crain.begin(), crain.end());
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		int n;
		scanf("%d", &n);
		pq.push(n);
		if (maxCrain < n) {
			possible = false;
		}
	}
	int idx = 0;
	while (idx < N && !pq.empty()) {
		int w = pq.top();
		if (w <= crain[idx]) {
			waitList[idx].push(w);
			pq.pop();
		}
		else {
			idx++;
		}
	}
	if (possible) {
		int answer = 0;
		int count = 0;
		while (count < M) {
			for (int i = 0; i < N; i++) {
				if (!waitList[i].empty()) {
					waitList[i].pop();
					count++;
				}
				else {
					int j = i - 1;
					while (j >= 0) {
						if (!waitList[j].empty()) {
							waitList[j].pop();
							count++;
							break;
						}
						else {
							j--;
						}
					}
				}
			}
			answer++;
		}
		printf("%d\n", answer);
	}
	else {
		printf("-1\n");
	}
	return 0;
}

 

결과