[BOJ] 2792번_보석 상자_이분 탐색 (C++)

[문제]

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

M가지 서로 다른 색상의 보석이 존재하고, N명에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 사람이 있어도 되지만, 한명이 여러색의 보석을 가져갈 순 없고 같은 색의 보석만 가져갈 수 있다.

한명이 너무 많은 보석을 가져가면 다른 사람이 질투하게 되는데. 이를 수치화해서 '질투심' 이라고 한다. 질투심은 가장 많은 보석을 가져간 사람이 가지고 있는 보석의 개수이다.

보석이 정보와 사람 수가 주어졌을 때, 질투심을 최소가 되도록 보석을 나누는 방법을 알아내는 프로그램을 작성하는 문제이다.

[사용 알고리즘]

이분 탐색

[풀이 핵심]

• 질투심을 최소로 만드는 방법은 보석의 종류와 상관없이 N명 이하에게 한 명당 나눠줄 수 있는 보석 수의 최소값을 구하는 것이다. 따라서 '보석의 수'를 기준으로 최소값(start)부터 최대값(end)까지 이분탐색을 돌아주면 된다.
• count는 나눠주는 사람의 수인데, 계산시 현재 색의 보석의 수 / 나누어줄 보석의 수 가 나누어떨어지지 않으면 남은 보석을 다른 사람에게 나눠줘야 하기 때문에 count를 늘려줘야한다.

[코드]

//boj2792번_보석 상자_이분 탐색

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

using namespace std;

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

	vector<int> v;

	for (int i = 0; i < M; i++) {
		int num;
		cin >> num;

		v.push_back(num);
	}

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

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

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

		int count = 0;

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

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

	cout << result;

	return 0;
}