[BOJ/22953번] 도도의 음식 준비 (C++/이분탐색)

개요

https://www.acmicpc.net/problem/22953

22953번: 도도의 음식 준비

G4

본문

처음에는 정렬 후 빠른 순으로 그리디써서 때려 맞춰봤는데, 오답

 

- 요리사 수와 격려 기회가 생각보다 작다. -> 브루트포스

 

모든 경우의 수를 확인하면서 이분 탐색으로 최소 시간을 구했다.

 

그 중 가장 작은 시간을 출력

 

더 이상 격려 할 수 없는 경우도 고려해야 함에 주의

 

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int LIMIT = 1e6 + 2;
const ll INF = 1e15;

int N, K, C;
ll A[12];
ll result = INF;
bool Check(ll t)
{
	ll foodSum = 0;
	for (int i = 0; i < N; i++)
		foodSum += t / A[i];

	if (foodSum >= K)
	{
		result = min(result, t);
		return true;
	}
	else
		return false;
}
void BinarySearch()
{
	ll maxT = INF;
	ll minT = 1;
	ll midT = INF / 2;
	while (minT <= maxT)
	{
		midT = (minT + maxT) / 2;
		if (Check(midT))
		{
			maxT = midT - 1;
		}
		else
		{
			minT = midT + 1;
		}
	}
}
void Solve(int sup, int idx = 0)
{
	if (sup == 0)
	{
		BinarySearch();
		return;
	}
	for (int i = idx; i < N; i++)
	{
		if (A[i] > 1)
		{
			A[i]--;
			Solve(sup - 1, i);
			BinarySearch();
			A[i]++;
		}
	}
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> K >> C;
	for (int i = 0; i < N; i++)
		cin >> A[i];

	Solve(C);

	cout << result;
}