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

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

16401번: 과자 나눠주기

 

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

int main() {
	long long m, n;
	cin >> m >> n;
	
	vector<long long> v;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	long long min = 1;
	long long max = v[n - 1];
	long long ans = 0;
	
	while(min <= max){
		long long cnt = 0;
		long long mid = (min + max) / 2;
		for(int i = 0; i < n; i++){
			cnt += v[i] / mid;
		}
		if(cnt >= m){
			min = mid + 1;
			ans = mid;
		}else{
			max = mid - 1;
		}
	}
	
	cout << ans << endl;
	return 0;
}

 

이분 탐색 문제이다. min은 과자의 길이가 가장 작은 경우인 1, max는 가장 긴 과자의 길이로 설정한다.

mid 길이로 나눠줄 때 몇 명(cnt)에게 나눠줄 수 있는지 구한다.

cnt가 m보다 크거나 같다면 과자 길이가 짧아서 다 나눠줄 수 있다는 의미이므로 min을 mid + 1로 이동시키고 ans를 mid로 설정한다.

cnt가 m보다 작다면 나눠주는 과자 길이가 길어서 다 나눠줄 수 없다는 의미이므로 max를 mid - 1로 이동시킨다.