[백준]22254:👨‍🔧공정 컨설턴트 호석 - JAVA

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

22254번: 공정 컨설턴트 호석

풀이

🪑 이전 문제가 너무 어려웠어서 잔뜩 쫄아있었는데 4번문제로 나왔던 이번 문제는 어렵지 않게 풀었다. 이분탐색 + 우선순위 큐(자료구조) 문제이다.

 

📝 문제의 조건을 살펴보자.

• 각 선물마다 제작에 필요한 시간이 정해져 있다.
• 1~K까지의 공정 라인에서 맞춤형 선물들을 제작하는데 소요되는 최소 라인의 수를 구한다.

 

🔧 문제를 풀어보자!

1. 탐색 공정 개수를 기준값으로 이분탐색을 한다.
2. mid개의 공정으로 맞춤형 선물을 제작할 수 있다면 더 작은 범위를 탐색하고, 불가하면 더 큰 범위를 탐색한다.

 

🔹 탐색 공정의 개수를 기준값으로 이분탐색을 한다.

- 탐색 공정의 수 중에서 어떠한 '조건'에 맞는 최소값을 구하는 문제이므로 조건에 맞는지 확인하는 과정이 필요하다. 

- 탐색 공정의 개수를 기준값으로 정하였고 최소 공정의 수는 1개, 최대 공정의 수는 제작해야 할 선물 개수인 n개로 잡아 주었다.

 

🔹 mid개의 공정으로 맞춤형 선물을 제작할 수 있다면 더 작은 범위를 탐색하고, 불가하면 더 큰 범위를 탐색한다.

- mid개의 공정으로 제작할 수 있는지 확인하기 위해 우선순위큐를 사용하였다.

- 큐에 mid개 만큼 숫자를 넣어주고, 가장 작은 값을 가진 경우부터 꺼내어 맞춤혀 선물을 제작하는데 소요되는 시간을 더해 다시 넣어주기를 반복했다.

- 이러한 반복 과정에서 x를 넘어가는 경우가 발생하면 제작할 수 없다는 의미이므로 false를 반환한 후 더 큰 범위를 탐색하도록 하였다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[] process_time;
 
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        //입력
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
        int n = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
 
        String str2 = bf.readLine();
        StringTokenizer st2 = new StringTokenizer(str2);
        process_time = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            process_time[i] = Integer.parseInt(st2.nextToken());
        }
        //입력 끝
 
        int left = 1;
        int right = n;
        while(left <= right) {
            int mid = (left + right) / 2;
 
            if(can_process(mid, x, n)) {
                right = mid - 1; 
            } else {
                left = mid + 1;
            }
        }
        System.out.println(left);
    }
 
    public static boolean can_process(int mid, int x, int n) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        
        for(int i = 0; i < mid; i++) {
            q.offer(0);
        }
 
        for(int i = 1; i <= n; i++) {
            int time = q.poll();
            if(time + process_time[i] > x) return false;
            q.offer(time + process_time[i]);
        }
        return true;
    }
}