[BaekJoon] 1092 배

1.  문제 링크

https://www.acmicpc.net/problem/1092

2.  문제

요약

• 항구에 크레인이 N대가 있고 모든 크레인은 동시에 움직이며 크레인이 1분에 박스를 한 개씩 배에 실을 수 있습니다.
• 각 크레인에는 무게 제한이 있어 그 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없을 때, 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 50보다 작거나 같은 자연수인 크레인의 개수 N이 주어지고 두 번째 줄에는 1,000,000보다 작거나 같은 수인 각 크레인의 제한 무게가 주어지며 세 번째 줄에는 10,000보다 작거나 같은 자연수인 박스의 수 M이 주어지고 네 번째 줄에는 1,000,000보다 작거나 같은 자연수인 각 박스의 무게가 주어집니다.
• 출력: 첫 번째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Main {
	public int getMinTime(Integer[] cranes, ArrayList<Integer> boxes) {
		Arrays.sort(cranes, Collections.reverseOrder());
		Collections.sort(boxes, Collections.reverseOrder());
		if(boxes.get(0) > cranes[0]) {
			return -1;
		}
		int time = 0;
		while(boxes.size() > 0) {
			for(int i = 0; i < cranes.length; i++) {
				for(int j = 0; j < boxes.size(); j++) {
					if(cranes[i] >= boxes.get(j)) {
						boxes.remove(j);
						break;
					}
				}
			}
			time += 1;
		}
		return time;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int crane_num = Integer.parseInt(br.readLine());
		Integer[] cranes = new Integer[crane_num];
		String[] input = br.readLine().split(" ");
		for(int i = 0; i < cranes.length; i++) {
			cranes[i] = Integer.parseInt(input[i]);
		}
		int box_num = Integer.parseInt(br.readLine());
		ArrayList<Integer> boxes = new ArrayList<Integer>();
		input = br.readLine().split(" ");
		br.close();
		for(int i = 0; i < box_num; i++) {
			boxes.add(Integer.parseInt(input[i]));
		}
		Main m = new Main();
		bw.write(m.getMinTime(cranes, boxes) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 여러 대의 무게 제한이 있는 크레인이 동시에 움직이기 때문에 한 번 크레인을 움직일 때 모든 크레인을 이용하여 박스들을 배에 옮겨야지만 최소의 시간으로 배에 모든 박스를 움직일 수 있습니다.
• 만약 박스 중 가장 무게가 많이 나가는 박스의 무게가 크레인 중 박스를 옮길 수 있는 무게가 가장 높은 크레인의 무게 제한보다 무겁다면 해당 박스를 옮길 수 있는 크레인이 없기 때문에 모든 박스를 배로 옮길 수 없습니다.
• 모든 박스를 배로 옮길 수 있다면 크레인과 박스 모두 무게순의 내림차순으로 정렬하여 한 번 크레인을 움직일 때 각 크레인이 옮길 수 있는 박스를 찾아 해당 박스들을 한 번에 같이 배로 옮기도록 합니다.
• 내림차순으로 정렬해주는 이유는 각 크레인들이 옮길 수 있는 박스들을 빠르게 찾을 수 있도록 하기 위해 정렬을 해주었습니다.

1. 각 크레인의 무게 제한을 1차원 배열에 설정하고 박스의 무게를 ArrayList에 설정한 후, 크레인의 무게 제한과 박스의 무게를 내림차순으로 정렬합니다.
2. 만약 박스의 무게 중 가장 무거운 무게가 크레인 무게 제한의 가장 무거운 무게보다 무겁다면 모든 박스를 배에 옮길 수 없기 때문에 -1을 출력합니다.
3. 그렇지 않다면 각 크레인에 대해 정렬되어 있는 박스의 무게들 중에서 해당 크레인이 옮길 수 있는 가장 무거운 박스를 찾아 해당 박스 무게를 박스의 무게가 들어있는 ArrayList에서 제거합니다.
4. 3번의 방법을 모든 크레인에 대해 진행했다면 모든 크레인을 동시에 한 번 움직였기 때문에 시간을 1 증가시키고 모든 박스를 옮길 때까지, 즉 박스의 무게가 들어있는 ArrayList의 크기가 0이 될 때까지 3번을 진행합니다.
5. 모든 박스를 옮겼을 때의 시간을 출력합니다.