Baekjoon 1092 배 JAVA

1092번: 배

문제

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

풀이

1. 입력받는 크레인의 무게 제한과 박스들의 무게를 내림차순 정렬한다.

2. 정렬후 가장 작은 무게의 박스와, 가장 무거운 무게를 들 수 있는 크레인의 무게 제한을 비교하여 박스가 더 무겁다면 -1을 출력

3. 한번의 전체 사이클을 돌면서 크레인이 들 수 있는 가장 무거운 무게의 박스를 옮긴다.

3-1. 옮긴 박스는 삭제하여 추가적으로 탐색하지 않도록 한다 (중요!!!)

4. 들 수 없다면 현재 크레인이 들 수 있는 가장 무거운 box를 탐색한다.

4-1. 박스는 내림차순으로 정렬되어있기에, 마지막 box까지 탐색하여 들 수 있는 무게가 있을때까지 탐색

4-2. 가장 가벼운 박스도 들지 못한다면 시간 변수를 증가시키고, 가장 무거운 크레인부터 다시 시작

5. 박스가 남아 있을 때까지 3-4를 반복

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		ArrayList<Integer> crains = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++)
			crains.add(Integer.parseInt(st.nextToken()));
		
		int m=Integer.parseInt(br.readLine());
		ArrayList<Integer> boxes = new ArrayList<>();
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<m;i++)
			boxes.add(Integer.parseInt(st.nextToken()));
		
		Collections.sort(crains, Collections.reverseOrder());	// 크레인의 정보를 입력받고 내림차순으로 정렬
		Collections.sort(boxes, Collections.reverseOrder());	// 박스의 정보를 입력받고 내림차순으로 정렬
		
		if(crains.get(0)<boxes.get(0))	// 가장 무거운 박스를 들지 못한다면 -1출력 후 종료
			System.out.println(-1);
		else {
			int ans=0;	// 시간변수
			while(boxes.size()>0) {	// Box가 남아있을때까지
				int j=0;	// 박스의 index
				for(int i=0;i<n;) {	// 크레인을 바꿔가면서 들 수 있는 가장 무거운 box를 옮김
					if(crains.get(i)>=boxes.get(j)) {	// 크레인이 박스를 들 수 있을때
						boxes.remove(j);	// 옮긴 박스는 삭제
						i++;	// 사용된 크레인은 1분뒤에 사용 가능하기에 크레인 번호를 바꿈
					}
					else
						j++;	// 들 수 없을때는 가벼운 box를 찾음
					if(j==boxes.size())	// 가장 가벼운 box까지 찾았을때 다시 처음으로 돌아가서 가장 무거운 크레인이 동작
						break;
				}				
				ans++;	// 크레인들이 하나 이상의 box를 옮기면 1분이 지난다.
			}
			System.out.println(ans);
		}
	}
}