[Boj_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, 모든 시간은 자연수이다.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 3
• 🔔  문제 유형 : 자료 구조, 이분 탐색, 우선순위 큐, 매개 변수 탐색
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

각 선물마다 제작에 필요한 시간이 정해져 있을 때,

최대 x시간 이내에 모든 선물을 제작하기 위해 필요한 최소 공정 라인의 개수를 구하는 문제이다.

 

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

 

🔹 공정 라인의 개수를 기준으로 이분 탐색을 진행한다.

공정 라인의 최소 개수는 1개, 최대 개수는 선물의 개수인 n개다.

mid개의 공정 라인으로 x시간 이내에 제작이 가능하면, 더 작은 개수로도 가능한지 확인한다.

불가능하다면, 공정 라인 개수를 늘려야 하므로 더 큰 범위를 탐색한다.

 

🔹 mid개의 공정 라인에서 선물을 배정하는 방식으로 우선순위 큐를 사용한다.

현재까지 사용된 공정 시간이 가장 적은 라인에 새로운 선물을 배정한다.

선물을 배정하면서 총 시간이 x를 초과하면 false를 반환해 mid를 증가시켜 탐색하도록 한다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 77216KB
시간 : 868ms

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

public class Main {
    static int n, x;
    static int[] ProcessTime;
    public static void main(String[] args) 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()); // 제작 완료까지 남은 시간

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

        int start = 1;
        int end = n;
        while (start <= end) {
            int mid = start + (end-start) / 2; // 공정 라인 개수

            if (isPossible(mid)) { // 현재 공정 라인 개수로 시간에 맞춰 제작을 끝낼 수 있다면
                end = mid-1;
            } else start = mid+1;
        }

        System.out.println(start);
    }

    private static boolean isPossible(int mid) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < mid; i++) { // 공정 라인 개수만큼 0(시간)으로 채우기
            pq.offer(0);
        }
        for (int i = 0; i < n; i++) {
            int nowTime = pq.poll();

            // 시간 안에 끝내지 못함
            if (nowTime+ProcessTime[i] > x) return false;
            pq.offer(nowTime+ProcessTime[i]);
        }
        return true;
    }
}

 

골드 3 문제인데 생각보다 어렵지 않게 풀었다. 이분 탐색 문제에 감이 잡혀가는 것 같아서 뿌듯하다. 😁

우선순위 큐로 해결하는 부분은 이 문제와 유사했던 것 같다.

해결 완료 ! 🔥