# 1092. 배

관련 알고리즘 : 그리디, 정렬

 

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

1092번: 배

---

해결 과정

 

문제의 조건을 보면,

• 크레인에 무게 제한 G 존재 (G <= 1,000,000)
• 무게 제한 초과할 시, 크레인으로 이동 불가
• 항구에 크레인 N대 (N <= 50)
• 1분에 박스를 하나씩 배에 싣기 가능

정렬을 이용하여 크레인의 무게 및 박스 크기를 내림차순 해 줌으로써 문제를 해결할 수 있었다.

크레인이 버틸 수 있는 최대 무게를 초과하는 박스가 있다면 크레인으로 이동이 불가하므로 이 때는 -1을 반환한다.

크레인 또한 어떤 박스도 옮길 수 없는 경우, 크레인 목록에서 제외함으로써 시간을 절약할 수 있다.

 

---

C++ 코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
 
int main() 
{
	int n, m; // n : 박스 개수 m : 크레인 개수 
	int num; //각 벡터의 요소
	int cnt = 0; //몇 분만에 옮겼는지 결과값
    
	vector<int> c, b; // c-크레인, b-박스에 대한 벡터
	
	cin >> m; // 크레인 입력 받기
	for (int i = 0; i < m; i++) 
    {
		cin >> num;
		c.push_back(num);
	}
	
	cin >> n; // 박스 입력 받기
	for (int i = 0; i < n; i++) 
    {
		cin >> num;
		b.push_back(num);
	}
 
	sort(c.begin(), c.end(), greater<int>()); // 크레인 무게제한 내림차순 정렬
	sort(b.begin(), b.end(), greater<int>()); // 박스 무게 내림차순 정렬
 
	if (b[0] > c[0]) // 크레인 최대 무게 제한보다 무거운 박스가 있는 경우
    { 
		cout << -1; // 이동 불가하므로 -1 반환
	}
	else // 이동 가능한 경우
    { 
		while (b.size()) // 박스가 빌 때까지
        { 
			int index = 0; // 크레인 순서
            
			for (int i = 0; i < b.size(); i++) // 박스 모두 돌며 검사
            { 
				if (index == c.size()) // 크레인 다 돌았는데 박스 담을 수 없는 경우
                { 
					break;
				}
				if (c[index] >= b[i]) // 크레인이 박스 들 수 있는지 여부 검사
                { 
					index++; // 다음 크레인
					b.erase(b.begin() + i); // 이동 가능할 시, 이동 후 박스 삭제
					i = i - 1;
				}
			}
			cnt++; //옮긴 시간
		}
		cout << cnt;
	}
}