[JAVA] BOJ(백준) - 배 - 1092

문제내용

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

1092번: 배

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

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

입력

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

출력

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

---

문제풀이

단순하게 생각해서 크레인 사용을 최소한으로 하기 위해선 각각 크레인의 무게제한에 가장 가까운 박스들을 순차적으로 옮겨줘야 한다.

예를들어 무게제한이 5kg인 크레인은 1,2,3,4,5 박스 중 5를 옮겨야지 효율이 가장 좋게 나온다.

만약 1,2,3,4 박스라면 4를 옮겨야 효율이 가장 좋다.

즉, 정렬이 필요하다.

 

1. 입력받은 크레인들과 박스들을 내림차순 정렬해준다.

2. 가장 무거운걸 들수 있는 크레인이 가장 무거운 박스를 못든다? -> -1 출력하고 함수 끝내기

3. 그게 아니면 정렬된 N번 크레인까지 하나씩 탐색하면서 박스를 옮겨준다.

4. 박스를 옮겼다면, 옮겨진 박스는 제거하고 다음 크레인으로 탐색을 시작한다.

5. 박스를 못 옮겼다면, 한단계 가벼운 무게의 박스를 옮기도록 시도한다.

 

이 과정을 거쳐주면된다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int n,m;
	static Integer[] cranes;//크레인들
	static List<Integer> list;//박스들
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		cranes = new Integer[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++)
			cranes[i] = Integer.parseInt(st.nextToken());
		
		m = Integer.parseInt(br.readLine());
		list = new ArrayList<>();
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<m; i++)
			list.add(Integer.parseInt(st.nextToken()));
		
		//내림차순 정렬
		Arrays.sort(cranes, Collections.reverseOrder());
		Collections.sort(list, Collections.reverseOrder());
		
		//박스 다못옮김 -> -1 출력.
		if(cranes[0]<list.get(0)) {
			System.out.println(-1);
			System.exit(0);
		}
		
		int cnt=0;
		while(true) {
			int boxIdx = 0;
			//0~n번 크레인까지 탐색.
			for(int i=0; i<n;) {
				//탐색할수 있는 박스가 없으면 for문 종료.
				if(boxIdx==list.size()) break;
				
				int box = list.get(boxIdx);
				int crane = cranes[i];  
				if(crane>=box) {//박스 옮기기 가능
					list.remove(boxIdx);//옮긴 박스 제거
					i++;//다음 크레인
				}else {//불가능.
					boxIdx++;//한단계 낮은 무게의 박스로.
				}
			}
			cnt++;//for문 한번 종료 = 모든 크레인 한번 작업
			if(list.size()==0) break;//남은 박스 없으면 종료.
		}
		System.out.println(cnt);
	}
}

---

마치며

단순 명확하게 생각하자.. 단순 명확!