[백준] 1092: 배 (그리디 알고리즘, 정렬) - JAVA

골드 5 문제집

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

 

 

 

# 문제

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

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

 

 

# 예제

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

3
6 8 9
5
2 5 2 4 7

 

 

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

2

 

# 필요개념

이 문제는 배로 옮길 수 있는 최대 무게 <= 박스의 무게를 만족하는 경우의 수 중에서 최소의 시간을 사용하는 경우를 찾아내는 문제이다. 사용할 수 있는 시간도 정해져있기 때문에, 배로 옮기는 최대 무게와 박스 무게를 각각 입력받아 정렬한 후 비교하면서 푸는 게 가장 합리적이다.

 

틀렸던 풀이

처음에는 각각을 배열에 입력한 후, 오름차순 정렬을 진행했다. 배로 옮길 수 있는 최대 무게 (crane) 가 만약 1 3 5 8이 들어왔고, 박스의 무게가 4라면, crane이 4 이상인 수를 처음 찾으면 그 뒤에있는 배는 사용할 수 있게 된다. 즉, 박스가 4라면, 처음 4 이상이 나온 5부터 그 뒤에있는 8인 배까지 쓸 수 있는 셈이다. 이런 이유로 처음 박스 무게 이상을 가진 배를 찾아야 겠다고 생각해 오름차순 정렬을 이용했다. 그 후 다른 배열(set)을 만들어서 박스의 개수를 추가해주었다. 해당 예시에선 set[2]++; 작업을 진행한 것이다.

 

그 후엔 set 배열만을 다루어 높이(시간)를 고루 맞춰주는 작업을 한다. 근데 이 작업이 생각보다 처리해야 할 예외 케이스가 많아 애를 먹었고, 결국 이 방법을 파기하고 다른 방법을 고민하게 되었다.

 

 

맞은 풀이

 시간을 고루 맞춰주는 작업이 어려웠기 때문에, 이번에는 시간을 중심으로 잡고 박스를 배치했다. 무슨말이냐면, 1일차에 가능한 모든 배에 박스를 분배하고, 시간을 추가해나갔다.

 

우선 전과 다르게 리스트로 input을 넣어주고, 이를 내림차순 정렬을 했다. 무게가 무거울수록 사용할 수 있는 배가 제한적이기 때문에 무거운 것들부터 배치시킨 것이다. 배치 완료된 박스를 리스트에서 제거해주기 위해 배열이 아닌 리스트를 사용하였다.

 

시간이 1일때, 무거운 박스부터 배에 분배한다. 이때 분배 완료된 박스는 리스트에서 제거하고, 이미 물건이 차게 된 배에는 같은 시간에 박스가 다시 분배되면 안 되므로, 배의 인덱스를 +1해준다. 이렇게 박스를 모두 한 번 순회하면 다시 처음부터 탐색한 후 시간은 +1된다. 이 작업을 박스리스트가 비게 될 때까지 반복한다.

 

이게 해당 작업의 코드이다. 

 

# Code

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

// 1092
public class Main {
    static int[] set;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Integer> cranes = new ArrayList<>();
        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());
        List<Integer> boxes = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0 ; i < M ; i++) {
            boxes.add(Integer.parseInt(st.nextToken()));
        }
        boxes.sort(Collections.reverseOrder());
        cranes.sort(Collections.reverseOrder());

        move(cranes, boxes);
    }

    private static void move(List<Integer> cranes, List<Integer> boxes) {
        int day = 0;
        if (cranes.get(0) < boxes.get(0)) {
            System.out.println(-1);
            return;
        }
        while(!boxes.isEmpty()) {
            int boxIdx = 0;
            int craneIdx = 0;

            while (craneIdx < cranes.size()) {
                if (boxIdx == boxes.size()) break;
                if (cranes.get(craneIdx) >= boxes.get(boxIdx)) {
                    boxes.remove(boxIdx);
                    craneIdx++;
                } else {
                    boxIdx++;
                }
            }
            day++;
        }
        System.out.println(day);
    }
}

 

 

# 결과