[백준 16401번] 과자 나눠주기 (C++)

문제링크 : https://www.acmicpc.net/problem/16401

16401번: 과자 나눠주기

 

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

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

void binary_search(int l, int h)
{
	while (l <= h)
	{
		int mid = (l + h) / 2;
		int cnt = 0;
		for (int i = 0; i < N; i++)
		{
			cnt += v[i] / mid;      //각각의 값을 현재 mid로 나눠줌
		}
		if (cnt >= M)               
		{
			result = mid;
			l = mid + 1;
		}
		else
		{
			h = mid - 1;
		}
	}
}

int main()
{

	fastio;
	cin >> M >> N;

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

	sort(v.begin(), v.end());
	binary_search(1, v.back());
	cout << result;

	return 0;
}

 

각 과자의 길이를 현재 mid 값으로 나눠준다.

이렇게 나눠준 값의 총합이 총 나눠줄 수 있는 사람의 갯수가 된다.

따라서 그 총합이 현재 나눠줄 사람의 수인 M보다 크거나 같다면 조건을 만족하게 되는 것이다.