[백준] 2792 보석 상자

[백준] 2792 보석 상자

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

//아이들의 수, 색상의 수
int N, M;

vector<int> bosuk;

//가장 많은 보석을 가지고 있는 학생의 보석 수 x가 되도록
//모든 보석을 학생에게 나누어줄 수 있는가?
bool decision(int x) {
	int cnt = 0;
	for (int i = 0; i < M; ++i) {
		cnt += (bosuk[i] / x);
		if (bosuk[i] % x) cnt++;
	}

	return cnt <= N;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	//가장 많은 같은 색의 보석의 개수
	int maxInput = 0;
	for (int i = 0; i < M; ++i) {
		int input;
		cin >> input;
		bosuk.push_back(input);
		maxInput = max(input, maxInput);
	}

	int l = 1;
	int r = maxInput;
	while (l + 1< r) {
		int mid = (l + r) / 2;
		if (decision(mid)) r = mid;
		else l = mid;
	}

	cout << r;
	return 0;
}