백준 1092(JAVA)

문제

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

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

풀이

어려운 문제이다.
이 문제의 중요한점은 박스의 무게에 집착하면 안되고 크레인이 들수 있는 박스의 개수에 집중해야한다.
6 8 9 크레인
2 2 4 5 7 박스
(둘다 오름차순 정렬한 상태임)
첫번째 6 크레인은 박스 4개를 들수있다.(2 2 4 5)
두번째 8 크레인은 박스 5개를 들수있다.(2 2 4 5 7)
세번째 9 크레인은 박스 5개를 들수있다.(2 2 4 5 7)

여기서 더 큰 박스의 무게를 들수있는 크레인은 더 작은 박스의 무게를 들수있는 크레인보다 옮길수있는 박스의 개수가 무조건 많다는 것을 착안하는 것이 중요하다.

그렇다면 위에서 각 크레인마다 구한 개수를 중복의 박스를 제외한 개수로 바꾸면
첫번째 6 크레인은 박스 4개(2 2 4 5)
두번째 8 크레인은 박스 1개(7)
세번째 9 크레인은 박스 0개(X)
이렇게된다.

여기서 1개 0개는 1개만들수있고, 아무것도 몬든다를 의미하는게아니라 위에서 얘기한 것처럼 더 작은 앞의 크레인의 박스의 개수는 모두 들수 있다.

이제 박스의 무게를 완전히 버리고 크레인이 들수 있는 개수에만 집중하면
0인 크레인은 자신보다 왼쪽에있는 크레인이 가지고있는 박스하나를 뺏어서 자기가 들면 된다.
이런식으로 박스를 옮기면 최단 시간내에 박스를 모두 옮길수있다.

4 1 0 이 어떤식으로 되는지 보면
1)
3 1 0
3 0 0
2 0 0
2)
1 0 0
0 0 0

총 2분이 소요된다. 이렇게 크레인이 들수있는 박스의 개수에 초점을 맞춰 풀면된다.

이 과정에서 나는 uppber bound를 이용했다

코드

package baekjoon.그리디;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main1092 {
    static int N, M;
    static List<Integer> kreins = new ArrayList<>();
    static List<Integer> boxes = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++){
            kreins.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(kreins);
        Collections.sort(boxes);

        if(kreins.get(N - 1) < boxes.get(M - 1)){
            System.out.println(-1);
        }else{
            System.out.println(calculateTime(makeLiftArr()));
        }

    }
    static int[] makeLiftArr(){
        int[] arr = new int[N];
        for(int i = 0; i < kreins.size(); i++){
            if(i > 0){
                arr[i] = upperBound(kreins.get(i)) - upperBound(kreins.get(i - 1));
            }else{
                arr[i] = upperBound(kreins.get(i));
            }
        }
        return arr;
    }
    static int calculateTime(int[] arr){
        int sum = Arrays.stream(arr).sum();
        int time = 0;
        while(sum > 0){
            for(int i = 0; i < arr.length; i++){
                if(arr[i] != 0){
                    arr[i]--;
                    sum--;
                }else{
                    for(int j = i; j >= 0; j--){
                        if(arr[j] != 0){
                            arr[j]--;
                            sum--;
                            break; // 보다 작은 크레인 에서 박스를 하나 뺏어온뒤 바로 break시켜야함
                        }
                    }
                }
            }
            time++;
        }

        return time;
    }
    static int upperBound(int target){
        int start = 0;
        int end = boxes.size();
        while(start < end){
            int mid = (start + end) / 2;
            if(boxes.get(mid) <= target){
                start = mid + 1;
            }else{
                end = mid;
            }
        }
        return end;
    }
}