문제 이해

1 ~ K까지의 공정 라인이 존재한다.
1번부터 N번까지 순서대로 맞춤형 선물을 만드려고 한다.
1개 공정 라인은 1개의 선물을 만들 때까지 다른 물건을 만들 수 없다.

총 N개의 맞춤형 선물을 X시간 이내에 만들고 싶을 때, 필요한 최소 공정 라인 개수(최솟값 K)를 구하는 문제이다.

---

문제 풀이

일단 K가 정해져있다는 가정 하에 이는 풀어본 문제이다.

• 콘센트 : https://velog.io/@idj7183/23843-%EC%BD%98%EC%84%BC%ED%8A%B8

짧게 설명하자면 우선순위큐를 만들고 일단 K만큼 선물을 담는다.
이후, K개가 넘어가면 가장 작은 시간을 가진 값을 우선순위 큐에서 뽑아내서 다음 선물을 만드는데 필요한 시간을 더해 다시 우선순위 큐에 넣는 방식이다.
모든 선물을 우선순위 큐에 넣었다면 우선순위 큐에 저장되어 있는 최댓값을 출력하면 K개의 공정 라인이 존재할 때의 시간을 구할 수 있는 것이다.

콘센트 문제와 다른 점은 K가 정해져있지 않다는 것이다
하지만, 이 문제도 쉽게 해결이 가능하다. 우리는 K가 제한되어 있을 때(N개 이상은 만들 필요가 없다) 최솟값 K를 구하는 문제인 것이다
즉, 이분 탐색을 통해 해결하면 된다.

따라서, left = 0, right = N으로 지정하고 이분 탐색을 통해 K를 임시로 정의한 다음 콘센트 문제처럼 우선순위 큐를 활용하여 X시간 내에 만들 수 있는지 없는지 확인하면 되는 것이다.

---

코드

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


public class Main {
	static StringBuilder sb = new StringBuilder();
	static FastReader sc = new FastReader();
	
	static int N;
	static long X;
	static long[] arr;
	
	public static void main(String[] args) {
		
		N = sc.nextInt();
		X = sc.nextLong();
		
		arr = new long[N];
		
		for(int i =0;i<N;i++) arr[i] = sc.nextLong();
		
		
		int min = 1; // K는 최소 1개는 만들어져야 함
		int max = N; // K를 N개 이상 만들 필요는 없음
		
		int ans = 0;
		while(min<=max) {
			PriorityQueue<Long> queue =new PriorityQueue<>();
			
			int mid = (min+max)/2;
			
            // 콘센트 문제와 동일한 알고리즘
			for(int i =0;i<N;i++) {
				if(queue.size()==mid) {
					long tmp = queue.poll();
					tmp += arr[i];
					queue.add(tmp);
				}
				else {
					queue.add(arr[i]);
				}
			}
			
			long time = 0;
			while(!queue.isEmpty()) {
				time = queue.poll();
			}
			
			if(time <= X) {
            // time이 X이하이므로 답이 될 수 있음
            // 임시로 ans에 저장하고 X를 감소시켜 확인해 봐야 하므로
            // max = mid - 1로 지정한 이후 이분탐색 진행
				ans = mid;
				max = mid - 1;
			}
			
			else {
            // time이 X보다 크므로 X를 증가시켜 확인해봐야 함
            // min = mid + 1로 지정하여 이분탐색 진행
				min = mid + 1;
			}
		}
		System.out.println(ans);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과