[BOJ 1092] 배 (G5)

📍 문제 

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

 

📍 문제 풀이

 

박스를 옮기는데 걸리는 최소 시간을 구해야하기 때문에

크레인의 무게 제한과 박스의 무게들을 모두 내림차순으로 정렬해야한다. 

오름차순으로해도 해결을 할 수 있겠지만 조금 더 복잡해지지 않을까..?

 

현재 크레인에 박스를 담을 수 있다면, 

해당 박스를 제거하고 다음 크레인을 탐색 시작

박스를 옮겨 담을 수 없다면, 한단계 가벼운 무게의 박스를 담을 수 있는지 확인

 

하지만 예외 사항으로, `크레인의 최대 무게 제한 < 박스의 최대 무게` 라면

옮겨 담을 수 없기 때문에 `-1` 출력

 

📍 전체 코드

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

public class boj_1092 {
	static List<Integer> cranes;
	static List<Integer> boxes;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		cranes = new ArrayList<>();
		boxes = new ArrayList<>();

		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			cranes.add(Integer.parseInt(st.nextToken()));
		}

		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < m; i++) {
			boxes.add(Integer.parseInt(st.nextToken()));
		}

		Collections.sort(cranes, Collections.reverseOrder());
		Collections.sort(boxes, Collections.reverseOrder());

		if (cranes.get(0) < boxes.get(0)) {
			System.out.println(-1);
			return;
		}

		int time = 0;
		while (!boxes.isEmpty()) {
			int idx = 0;
			for (int i = 0; i < cranes.size(); i++) {
				if(idx == boxes.size()) break;
				else if (cranes.get(i) >= boxes.get(idx)) {
					boxes.remove(idx);
				} else {
					idx++;
					i--;
				}
			}
			time++;
		}
		System.out.println(time);
	}
}