백준 - 13702번 : 이상한 술집 (C++)

풀이 방법 : 이분 탐색

Low값을 1, High 값을 주전자 용량 중에 가장 큰 용량으로 두고 루프를 돌려가며 Low와 High의 중간값으로 각 주전자의 용량을 나눈 수들을 누적해 더해간다.

누적된 합 즉, 그 중간값대로 막걸리를 나눠줬을 경우, 최대로 나눠줄 수 있는 인원수가 K와 크거나 같을 경우에 더 많이 나눠줄 수 있을 것이기 때문에 Low값을 Mid + 1 로 갱신시켜주고 정답도 갱신시켜준다.

반대의 경우라면 High값을 Mid - 1로 갱신시켜주면서 이분탐색을 진행해가면 된다.

#include <iostream>
#include <limits.h>

using namespace std;

unsigned int Kettle[10001] = {};

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, K;
	cin >> N >> K;

	unsigned int Max = 1;
	unsigned int Low = 1;
	unsigned int High = 0;

	for (int i = 0; i < N; ++i)
	{
		cin >> Kettle[i];
		High = max(Kettle[i], High);
	}

	unsigned int NumMax = 0;
	unsigned int Answer = 0;
		
	while(Low <= High)
	{
		unsigned int Mid = (Low + High) / 2;
		unsigned int Num = 0;

		for (int i = 0; i < N; ++i)
		{
			Num += Kettle[i] / Mid;
		}

		if (Num < K)
		{
			High = Mid - 1;
		}

		else if(Num >= K)
		{
			Answer = Mid;
			Low = Mid + 1;
		}
	}

	cout << Answer;
}