[Baekjoon] 1092_배

Gold V

문제(출처: https://www.acmicpc.net/problem/1092)

---

< 배 >

 

문제 풀이 

 

크레인의 무게와 박스의 무게를 각각 내림차순으로 정렬한 후에 박스를 배로 옮긴다.

 

 

 my solution (Java)

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.StringTokenizer;

public class _1092_ { // 배

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

		int n = Integer.parseInt(bf.readLine());

		Integer arr[] = new Integer[n];
		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int m = Integer.parseInt(bf.readLine());

		st = new StringTokenizer(bf.readLine());
		ArrayList<Integer> box = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			box.add(Integer.parseInt(st.nextToken()));
		}

		Arrays.sort(arr, Collections.reverseOrder());
		box.sort(Collections.reverseOrder());

		if (box.get(0) > arr[0]) {
			System.out.println(-1);
		} else {
			int result = 0;
			int idx = 0;

			while (!box.isEmpty()) {
				if (idx == 0) {
					result += 1;
				}
				for (int i = 0; i < box.size(); i++) {
					if (arr[idx] >= box.get(i)) {
						box.remove(i);
						break;
					}
				}
				idx += 1;

				if (idx == n) {
					idx = 0;
				}
			}
			System.out.println(result);
		}
	}
}

변수)
n : 크레인 수
arr : 크레인 무게
m : 박스 수
box : 박스 무게
result : 모든 박스를 배로 옮기는데 드는 시간의 최솟값
idx : 크레인 인덱스

 

크레인과 박스의 무게를 입력받아 각각 내림차순으로 정렬한다. 크레인은 배열로 입력받고 박스 무게는 ArrayList로 입력받은 이유는 박스는 제거해야 하기 때문이다. 

 

정렬 후에 만약 박스의 가장 무거운 무게가 크레인의 가장 무거운 무게보다 값이 크다면 모든 박스를 배로 옮길 수 없으므로 -1을 출력한다. 이 경우가 아니라면 모든 박스를 배로 옮길 수 있다는 뜻이다. 박스를 담은 ArrayList가 빌 때까지 다음 과정을 반복한다. 0번째 크레인으로 박스를 옮기려면 먼저 result+1을 한다. 크레인 무게보다 박스의 무게가 작거나 같다면 배로 옮길 수 있다는 뜻이므로 박스를 제거한다. 

 

최종 모든 박스를 배로 옮기는데 드는 시간의 최솟값인 result를 출력한다.

---

---