1092 배

여러대의 크레인으로 짐을 나르려고 한다. 크레인 마다 실을 수 있는 무게가 정해져있고, 짐의 무게도 제각각이다. 크레인 하나당 1분에 1개씩 나를 수 있다고 할 때, 짐을 다 나르기 위해선 최소 몇분이 필요한지를 구하는 문제이다.

생각보다 까다로운 문제이다. 처음엔 짐을 무게순으로 오름차순 정렬하여 크레인 무게가 되는대로 가져갔으나 WA(Wrong Answer)가 떴다. 왜냐하면 가벼운 짐밖에 들지 못하는 크레인이 들 수 있는것이 사라져버리기 때문이다. 그렇다고 반대로 해줘도 최소 시간은 나오지 않는다.

이 문제를 풀기 위해선 각 크레인이 가져가야 좋은 짐의 개수를 구해야 한다.
예를들어 크레인이 들 수 있는 무게가 6 8 9 이고, 짐의 무게가 2 3 5 7 9라고 하면,
6이 가져가야 좋은 짐은 2 3 5로 3개.
8이 가져가야 좋은 짐은 7로 1개.
9가 가져가야 좋은 짐은 9로 1개가 된다.

만약 9보다 무거운 짐이 존재한다면 옮길 수 가 없으므로 -1을 출력한다.

이렇게 개수를 구해줬다면 루프를 돌면서 하나씩 제거한다.
위 예제에선 1분이 지나면 6 8 9 는 각각 2개 0개 0개가 된다.
2분이 지나면 6은 1개를 제거해서 1개, 8 9 는 0개가 남는데, 이 땐 자신보다 가벼운 무게의 짐을 하나씩 골라가면 된다. 즉, 8이 6이 들어야 좋은 짐을 가져가게 되면 2분에 모든 짐을 나를 수 있다.

위와 같은 방법으로 문제를 해결해주면 된다.

소스