백준 2792 C++

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

간단하게 바이너리 서치로 풀 수 있는 문제였습니다.

 

#include <bits/stdc++.h>

using namespace std;

int n, m;
int result = 987654321;
vector<int> v;

bool check(int num)
{
	int a = 0;
	for (int i : v) {
		a += i / num;			//num개로 나눴을 때 받는 학생의 수
		if (i % num != 0) a += 1;
	}

	return a <= n;		//각 사람에게 num개씩 나눠줬을 때 사람수를 초과하는지 초과하지 않는지. -> 
}

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

	cin >> n >> m;		//n명의 학생, m개의 색상 수 

	//각 색상별 개수 push
	int temp;
	for (int i = 0; i < m; i++) {
		cin >> temp;
		v.push_back(temp);
	}
	sort(v.begin(), v.end());
	int left = 1, right = v[m - 1], mid;

	while (left <= right) {
		mid = (left + right) / 2;
		if (check(mid)) {
			result = min(result, mid);
			right = mid - 1;		//현재 숫자에서 나눠줄 수 있으니 숫자를 더 작게해서 사람 수 만큼 나눌 수 있는지 확인.
		}
		else {
			left = mid + 1;		//현재 mid로 나눠줄 때 사람 수를 초과해버린다. 숫자를 키워 사람 수 만큼 나눌 수 있는지 확인한다.
		}
	}

	cout << result;
}