BOJ 1092 배

까다롭다...

주어진 박스들을 무게에 따라 나눠보자.
어떤 박스는 주어진 크레인들 중 어떤 것으로도 운반하지 못할 수 있고, 어떤 박스는 운반 가능한 크레인이 1개, 어떤 박스는 어떤 크레인으로도 운반 가능할 것이다.

이렇게 박스들을 운반 가능한 크레인 개수에 따라 나눈다.
예를들어, 3종류의 크레인이 있다고 하자.
그룹1 : 크레인 중 1개의 크레인으로만 운반할 수 있는 박스들은 항상 그 크레인으로만 옮길 수 있으므로 전체 박스를 다 옮길 때, 최소한 그 박스들의 개수만큼의 시간이 걸릴 것이다.

그룹2 : 2개의 크레인으로 운반할 수 있는 박스들을 보자.  2개의 크레인을 사용할 수 있긴해도 이 중 1개의 크레인은 첫번째 그룹(1개의 크레인만 운반 가능한 박스들)의 박스를 운반해야 한다. 만약 그룹1의 박스보다 그룹2의 박스가 더 많다면 전체 박스를 다 옮길 때, 최소한 2개의 크레인으로 (그룹1의 박스 수 + 그룹2의 박스 수) 만큼의 박스들을 옮기는 시간이 걸릴 것이다. 여기서 그룹1의 박스가 더 많으면 어차피 그룹1을 1개의 크레인으로 옮기는 시간이 걸리니까 전체 박스를 옮기는 데 걸리는 시간을 구하는 것에는 지장이 없다.

그룹3 : 3개의 크레인으로 운반 가능한 박스들 역시, 3개의 크레인을 사용할 수 있긴해도 1, 2크레인을 그룹 1, 2가 사용하게 되면 결국 1개의 크레인밖에 못쓴다. 만약 그룹 1 또는 2의 박스가 그룹 3의 박스보다 많으면 위에서 이미 계산했던 시간이 답이 될 것이다.
하지만 그룹 3의 박스가 더 많다면 (그룹1 박스 수 + 그룹2 박스 수 + 그룹3 박스 수)를 3개의 크레인으로 옮기는 시간이 걸릴 것이다.

즉 이 세가지 시간 중 최대값을 구하면, 전체 박스를 옮기는 최소 시간을 구할 수 있다.

구현도 좀 헷갈리고... 좀 어려운면서 좋은 문제같다.