[백준] 1092번 : 배 (JAVA/자바)

[문제 링크]

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

문제 설명

크레인 N대를 사용해서 박스 M개를 모두 옮기는 데 드는 시간의 최솟값을 구한다.

1분에 박스를 하나씩 옮길 수 있고, 모든 크레인은 동시에 움직인다.

각 크레인의 무게 제한보다 무거운 박스는 옮길 수 없다.

모든 박스를 옮길 수 없는 경우 -1

 

 

 

문제 풀이

알고리즘 분류

• 그리디 알고리즘
• 정렬

 

크레인과 박스를 각각 내림차순 정렬한다.

boxes.get(0) > crane.get(0)  박스 무게의 최대값이 크레인 무게제한의 최대값보다 클 경우 모든 박스를 옮길 수 없다.

1. 가장 무거운 박스부터 차례대로 탐색하면서 각 크레인이 해당 박스를 옮길 수 있는지 확인한다.

2. 해당 박스를 옮길 수 있으면 크레인 사용 처리, 리스트에서 박스 제거3. 모든 크레인이 한 번씩 사용되면 시간 증가위의 과정을 모든 박스가 옮겨질 때까지 반복한다.

 

 

전체코드

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

public class Main {

    static int n, m, cnt = 0;
    static ArrayList<Integer> crane = new ArrayList<>();
    static ArrayList<Integer> boxes = new ArrayList<>();

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

        n = Integer.parseInt(br.readLine());    //크레인 수

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

        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(crane, Collections.reverseOrder());    //크레인 내림차순 정렬
        Collections.sort(boxes, Collections.reverseOrder());    //박스 내림차순 정렬

        //모든 박스를 배로 옮길 수 없는 경우
        if (boxes.get(0) > crane.get(0)) {
            System.out.println(-1);
            return;
        }

        while (!boxes.isEmpty()) {
            int craneIdx = 0;
            int boxIdx = 0;

            //박스를 모두 돌면서 1회차에 크레인으로 옮길 수 있는 박스 탐색
            while(boxIdx < boxes.size()) {
                if(craneIdx >= n) break;
                if(boxes.get(boxIdx) <= crane.get(craneIdx)) {  //크레인으로 박스를 옮길 수 있는 경우
                    boxes.remove(boxIdx);   //박스 제거
                    craneIdx++;
                } else {
                    boxIdx++;
                }
            }
            cnt++;
        }

        System.out.println(cnt);
        return;
    }
}