백준 22254 (공정 컨설턴트 호석) - java

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

 

문제

거듭된 창업 성공을 이룬 류진국 사장은 이번에는 맞춤형 선물을 제작해주는 공장을 만들기로 했다. 현재 들어온 맞춤형 선물 주문은 총 𝑁개이며, 각 맞춤형 선물마다 제작에 필요한 시간이 정해져있다. 주문의 번호는 1번부터 𝑁번까지 매겨져 있으며, 다음과 같은 규칙에 맞게 공정이 이뤄진다.

1. 공정 라인이 총 𝐾개가 있다면 1번부터 𝐾번까지의 번호가 존재한다.
2. 공정 라인의 사용 시간은 배정된 맞춤형 선물들의 제작 시간의 총합이다.
3.  𝑖번 선물은 1번 부터 𝑖−1번 선물들이 배정된 이후에 사용 시간이 가장 적은 공정 라인 중 하나에 배정된다.

모든 맞춤형 선물의 제작이 완료될 때까지 최대 𝑋시간이 남아있는 상황인데, 아직 공정 라인의 개수 𝐾가 정해져 있지 않다. 류진국 사장은 이 분야 최고 권위자, 공정 컨설턴트 호석에게 의뢰했다. 공정 컨설턴트 호석은 최소한의 비용을 쓰기 위해서 공정 라인의 개수를 최소화 시키고자 한다. 호석을 도와 필요한 최소 공정 라인 개수를 계산하자.

 

유형 : 이진 탐색 + 우선순위 큐

 

접근 방식

• 공정라인의 최소 개수는 1개이다. 그리고 최대 개수는 n개이다. ( 끝나는 시간이 x 시간 이하이면 된다. ) 즉 공정 라인의 개수를 이진 탐색하여 정하고 시뮬을 돌리면 된다.
• 시뮬을 구성하는 것은 간단하다. 우선 순위 큐를 통해 숫자가 작은 것을 정렬 기준으로 두면 된다. 거기에 계속 시간을 더해가면서 가장 큰 숫자가 x 시간 이하인지 탐색하면 된다.

전체 코드

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

public class Main {

    static int n;
    static long m;
    static int[] arr;

    static PriorityQueue<Long> pq = new PriorityQueue<>(
            (x,y) -> Long.compare(x,y)
    );

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

        n = Integer.parseInt(st.nextToken());
        m = Long.parseLong(st.nextToken());

        arr = new int[n+1];
        st = new StringTokenizer(br.readLine()," ");

        for(int i = 1 ; i <= n ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int l = 1;
        int r = n;
        int mid = 0;

        int result = n;

        while(l <= r) {
            mid = (l + r) / 2;

            if(go(mid)) {
                result = Math.min(result , mid);
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }

        System.out.println(result);
        br.close();
    }

    static boolean go(int num) {
        pq.clear();

        for(int i = 1 ; i <= num ; i++) {
            pq.add(0l);
        }

        for(int i = 1 ; i <= n ; i++) {
            if(!pq.isEmpty()) {
                long tmp = pq.poll();
                tmp += arr[i];
                pq.add(tmp);
            }
        }

        long result = 0;

        while(!pq.isEmpty()) {
            result = pq.poll();
        }

        return result <= m;
    }
}