[백준 1092] 배 (C++)

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

1092번: 배

1. 주의할 점

- 정렬을 한다

- 해당 크레인이 자신이 들 수 있는 무게보다 적고, 해당 크레인만 들 수 있는 박스 수를 통해 해결한다

- 가장 무거운 박스의 무게가 크레인이 들 수 있는 가장 무거운 무게를 넘어서면 -1을 출력한다

 

2. 구현

- 입력받은 크레인이 들 수 있는 무게(Crane), 박스의 무게(Box)를 오름차순으로 정렬한다

- Avail[i] 배열에는 i-1번 크레인이 들 수 없고, i번 크레인만 들 수 있는 박스의 수를 저장한다

- 가장 힘이 좋은 크레인부터 시작하여 해당 크레인이 들 수 있는 힘과 박스의 무게가 가장 적게 차이나는 박스를 옮긴다. 옮긴 박스의 수를 Cnt에 저장하여, Cnt가 총 박스의 수와 같으면 언제든지 종료하도록 한다

- 글보단 각 과정을 표시하여 이해가 쉽도록 한다

//4개의 크레인이 들 수 있는 무게
4
2 5 8 12

//10개 박스의 무게
10
1 2 3 4 5 6 7 8 9 10

//Avail[]배열에 저장될 값
2 3 3 2

//0단계(Arr[]의 값)
2 3 3 2

//1단계
1 2 2 1

//2단계
0 1 1 0

//3단계
0 0 0 0
=> 결과: 3초

 

[코드]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> crane, box;
int avail[10000];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int c, num, val;
	cin >> c;
	for (int i = 0; i < c; i++) {
		cin >> val;
		crane.push_back(val);
	}
	sort(crane.begin(),crane.end());
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> val;
		box.push_back(val);
	}
	sort(box.begin(), box.end());
	if (crane[c - 1] < box[num - 1]) {
		cout << -1;
		return 0;
	}
	int idx = 0;
	for (int i = 0; i < num; i++) {
		if (crane[idx] >= box[i]) 	avail[idx]++;		
		else {
			idx++;
			i--;
		}
	}
	int cnt = 0, t = 0;
	while (1) {
		for (int i = c - 1; i >= 0; i--) {
			for (int j = i; j >= 0; j--) {
				if (avail[j]) {
					avail[j]--;
					cnt++;
					break;
				}
			}
			if (cnt == num) break;
		}
		t++;
		if (cnt == num) break;
	}
	cout << t;
	return 0;
}