문제 풀이

이분탐색을 통해 공정 라인을 몇개로 둘지 결정을 하고 결정한 라인으로 모두 소화할 수 있으면 true를 반환하고 소화하지 못한다면 false를 반환하는 방식으로 문제를 해결한다.

그 과정에서 가장 사용시간이 적은 공정 라인을 선택해야 하므로 우선 순위 큐를 이용해서 계속 갱신 해준다.

문제 링크

boj/22254

소스코드

PS/22254.cpp

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include<algorithm>
#include<memory.h>
#include<queue>
using namespace std;

int arr[100001];
int n, x;
bool check(int mid)
{
	priority_queue<int,vector<int>, greater<int>> pq;
	
	for (int i = 0; i < mid; i++)
	{
		pq.push(0);
	}

	for (int i = 0; i < n; i++)
	{
		int use = pq.top();
		pq.pop();
		if (use + arr[i] > x)
			return false;
		pq.push(use + arr[i]);
	}
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> x;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	int l=1, r=n;
	while (l <= r)
	{
		int mid = (l + r) / 2;

		if (check(mid))
		{
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	cout << r + 1;

}