[C++] 백준 2792번 - 보석 상자

 

문제 2792번

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

 

 

색상의 수만큼 보석들(입력값)을 벡터에 넣어준다. 이때 이분탐색을 할 때 필요한 right에 넣을 최대값을 구해준다(가장 개수가 많은 색의 보석). 왜냐하면 보석이 가장 많을 때가 질투심이 최대일 때이니까... (left에는 1을 넣어주면 됨)
left와 right의 중간값 mid를 기준으로 입력받은 각 색상의 보석을 나눠준다. 그렇게 나오는 몫이 나눠줄 수 있는 학생의 수이기에 count에 더해주고 나머지가 0이 아닐 경우 더 나눠줄 수 있으니까 count를 1증가시켜준다(if문의 조건에 0이 들어가면 false니까 실행이 안 됨).
최종으로 나온 count값이 학생수 N명보다 작거나 같으면 true를 반환해준다. true인 mid면 result에 mid값을 업데이트해준다. 그리고 N이 count보다 크거나 같다면 보석의 개수를 더 작게 할 수 있다는 소리니까 right를 mid-1로 이동시킨다. 

반대로 false인 mid면 개수를 더 늘려 사람수가 줄어들게 만들어야 한다. 그래서 left를 mid+1로 이동시킨다.
반복문을 마치고 나온 result값을 출력해주면 질투심이 최소가 된 값을 볼 수 있다.

 

#include <vector>
#include <iostream>
using namespace std;

long long N, M;
long long result;
vector <int> v;

bool check(int mid) {
	int count = 0;
	for (int i = 0; i < M; i++) {
		count += v[i] / mid;
		if (v[i] % mid) {
			count++;
		}
	}
	return N >= count;
}

int main() {
	cin >> N >> M;
	int a, Max = 0;
	for (int i = 0; i < M; i++) {
		cin >> a;
		v.push_back(a);
		if (Max < a) {
			Max = a;
		}
	}
	long long left = 1, right = Max;
	while (left <= right) {
		long long mid = (left + right) / 2;
		if (check(mid)) {
			result = mid;
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	cout << result;

	return 0;
}