BOJ1092 배 java

문제

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

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

입력

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

출력

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

풀이법

매 분마다 모든 크레인에 대하여 옮길 수 있는 박스를 선택하여 옮겨야 한다.

크레인과 박스를 내림차순으로 정렬하여 무거운 것부터 옮기는 게 핵심.

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

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

        int N = Integer.parseInt(br.readLine());
        Integer[] cranes = new Integer[N];

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

        int M = Integer.parseInt(br.readLine());
        Integer[] boxes = new Integer[M];

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

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

        if(cranes[0] < boxes[0]) {
            System.out.println(-1);
            return;
        }
        int[] positions = new int[N]; // 각 크레인이 짚어야 할 박스의 순서
        boolean[] checked = new boolean[M]; // 이미 짚은 박스 flag 배열

        int minutes = 0;
        int count = 0;
        while(true) {
            if(count == M) break;

            for(int crane = 0;crane<N;crane++) {

                for(int box = positions[crane]; box<M;box++) {
                    // 이미 옮기지 않은 박스면서 크레인의 제한무게보다 박스 무게가 작을 때
                    if(!checked[box] && boxes[box] <= cranes[crane]) {
                        checked[box] = true;
                        positions[crane]++;
                        count++;
                        break;
                    }
                    positions[crane]++;
                }
            }
            minutes++;
        }

        System.out.println(minutes);
    }
}

box를 positions[crane]부터 반복문을 시작해주지 않으면 시간초과가 발생하니 주의하자!