[BOJ] 13702번_이상한 술집_이분 탐색 (C++)

[문제]

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

막걸리가 담겨있는 주전자의 개수 N, 막걸리를 나눠 받을 사람의 수 K가 주어진다. 막걸리는 모두에게 똑같은 양으로 나눠주려고 할 때, 최대한 많은 양의 막걸리를 분배할 수 있는 용량 ml를 구하는 문제이다.

막걸리를 나눠 줄 때, 분배 후 주전자에 막걸리가 조금 남아 있는 것을 모아서 친구들에게 다시 주는 경우는 없이 조금 남은 막걸리는 버리는 것으로 한다.

[사용 알고리즘]

이분 탐색

[풀이 핵심]

• 막걸리의 용량은 2^31-1보다 작거나 같은 자연수 또는 0이므로 long long 타입을 사용해야 한다.
• start는 1, end는 입력받은 막걸리의 최대값으로 두고 이분탐색을 돌면 된다. (start가 0이 아니라 1인 이유는 start가 0이면 mid가 0이 될 가능성이 생기는데, 이렇게 되면 count를 구할 때 v[i]를 0으로 나누는 경우가 생겨 DivisionByZero오류가 발생하기 때문이다.)
• mid는 사람들에게 나눠주는 막걸리양을 뜻하며, 이를 통해 구한 count는 mid만큼 count명에게 나누어 줄 수 있다는 의미이다.
• count가 K보다 크거나 같으면 K명 이상 나눠 줄 수 있다는 의미이기 때문에 result에 mid값을 저장하고 막걸리양을 늘려서 더 많은 양을 나눠줄 수 있는지 확인한다.
• count가 K보다 작으면 K명을 나눠 줄 수 없다는 의미이기 때문에 막걸리양을 줄여서 K명에게 나눠줄 수 있는지 확인한다.

[코드]

//boj13702번_이상한 술집_이분 탐색

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	int N, K;
	cin >> N >> K;

	vector<int> v;

	for (int i = 0; i < N; i++) {
		int mak;
		cin >> mak;
		v.push_back(mak);
	}

	sort(v.begin(), v.end());

	long long start = 1;
	long long end = v[v.size() - 1];

	long long result = 0;

	while (start <= end) {
		int count = 0;
		long long mid = (start + end) / 2;

		for (int i = 0; i < v.size(); i++) {
			count += v[i] / mid;
		}

		if (count >= K) {
			start = mid + 1;
			result = mid;
		}

		if (count < K) {
			end = mid - 1;
		}
		else if (count > K) {
			start = mid + 1;
		}
	}

	cout << result;

	return 0;
}