[BOJ/백준] 22254 - 공정 컨설턴트 호석

---

최소 공정 수를 이분탐색

---

---

• 제목

공정 컨설턴트 호석

---

• 조건

시간 제한 : 1 초

메모리 제한 : 512 MB 

---

• 문제

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

1. 공정 라인이 총 K개가 있다면 1번부터 K번까지의 번호가 존재한다.

2. 공정 라인의 사용 시간은 배정된 맞춤형 선물들의 제작 시간의 총합이다.
 3. i번 선물은 1번 부터 i1번 선물들이 배정된 이후에 사용 시간이 가장 적은 공정 라인 중 하나에 배정된다.

 

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

---

• 입력

첫 번째 줄에 맞춤형 선물 주문의 개수 N, 제작 완료까지 남은 시간 X가 공백으로 구분되어 주어진다.

두 번째 줄에는 1번부터 N번 선물이 필요한 공정 시간이 순서대로 주어진다. 단위는 '시간' 이다.

---

• 출력

모든 선물을 X시간 이내에 제작하기 위해 필요한 최소 공정 라인 개수를 출력하라.

---

예제 입력1	예제 출력1
6 11 5 2 8 4 3 5	3

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int N, X;
    static int[] arr;

    static boolean able(int cnt) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < cnt; i++) pq.add(0);
        for (int i = 0; i < N; i++) {
            int curr = pq.poll();
            curr += arr[i];
            pq.add(curr);
        }
        int maximum = 0;
        while(!pq.isEmpty()){
            maximum = Math.max(maximum, pq.poll());
        }
        return maximum <= X;
    }

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

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

        int answer = Integer.MAX_VALUE;
        int low = 1;
        int high = N;
        while (low <= high) {
            int mid = (low + high) / 2;
            if(able(mid)){
                high = mid - 1;
                answer = Math.min(answer, mid);
            } else {
                low = mid + 1;
            }
        }
        System.out.println(answer);
    }
}