[Java] 백준 22254. 공정 컨설턴트 호석

📌 문제 링크 - https://www.acmicpc.net/problem/22254

 

 

---

 

 

 

 

 

문제

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

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

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

 

 

 

입력

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

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

 

 

 

출력

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

 

 

 

제한

•  1 ≤ N ≤ 100,000, N은 자연수이다.
•  1 ≤ X ≤ 10^9, X는 자연수이다.
•  1 ≤ 각 선물의 공정 시간 ≤ X, 모든 시간은 자연수이다.

 

 

 

 

 

---

 

 

풀이

이분 탐색과 우선순위 큐를 활용하여 풀 수 있는 문제다. 

 

1. 이분 탐색으로 최소 공정 라인 개수를 탐색

- mid 개의 공정 라인으로 X 시간 내에 모든 선물을 제작할 수 있다면 공정 라인을 줄여주고(end = mid - 1), 최솟값을 갱신해 준다. 

- 불가능하다면 공정 라인을 늘려준다.(start = mid + 1)

 

2. 주어진 cnt(=mid) 개의 공정 라인으로 제작이 가능한지 확인

초기에 cnt 개의 선물을 공정 라인(우선순위 큐)에 배치해 준다.

이후 가장 빨리 끝나는 공정 라인에 다음 선물을 배치하며 진행해 주면 된다. 이때 다음 선물을 배치했을 때 공정 시간이 X를 초과하면 불가능한 것이다.

 

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*
 https://www.acmicpc.net/problem/22254
 모든 선물을 X시간 이내에 제작하기 위해 필요한 최소 공정 라인 개수를 출력
 */
public class Main_22254 {
    private static int N; // 선물 주문의 개수
    private static int X; // 제작 완료까지 남은 시간
    private static int[] products; // 선물별 필요한 공정 시간


    public static void main(String[] args) throws IOException {
        init();

        int minCnt = getMinCnt();
        System.out.print(minCnt);
    }//main


    private static int getMinCnt() {
        PriorityQueue<Integer> line = new PriorityQueue<>(); // 공정 라인
        int cnt = N; // 최소 공정 라인 개수
        int start = 1;
        int end = N;
        int mid;

        while(start <= end) {
            mid = (start + end) / 2;

            if(isPossible(mid, line)) {
                end = mid - 1;
                cnt = mid;
            }
            else {
                start = mid + 1;
            }

            line.clear();
        }

        return cnt;
    }//getMinCnt


    private static boolean isPossible(int cnt, PriorityQueue<Integer> line) {
        int time; // 공정 시간

        // 초기 cnt개 공정 라인에 선물 배치
        for(int i=0; i<cnt; i++) {
            line.add(products[i]);
        }

        for(int i=cnt; i<N; i++) {
            time = line.poll(); // 가장 짧은 공정 라인 시간 

            // X 시간 초과 체크
            if(time + products[i] > X) return false;

            // 가능하다면 선물 배정
            line.add(time + products[i]);
        }

        return true;
    }//isPossible


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 선물 주문의 개수
        X = Integer.parseInt(st.nextToken()); // 제작 완료까지 남은 시간

        products = new int[N]; // 선물별 필요한 공정 시간

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

        br.close();
    }//init


}//class