백준16401 - 과자 나눠주기

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

16401번: 과자 나눠주기

이분 탐색 문제이다. 시간복잡도 nlog(n)을 구현하면 되는 간단한 문제이다. 처음 시작을 1로 놓는 것을 까먹지 말자.

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

int main() {
	int M, N; //M명의 조카, N개의 과자
	int num; //과자의 길이
	int ans = 0; //최대 길이
	int start = 1, stop = 0; //탐색시작, 탐색 끝
	vector<int> v; //과자의 길이들이 저장될 공간

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> M >> N;
	for (int i = 1; i <= N; i++) {
		cin >> num;
		v.push_back(num);
		stop = max(stop, num); //가장 긴 과자를 끝으로 설정
	}

	while (start <= stop) {
		int mid = (start + stop) / 2;
		int cnt = 0;
		for (int i = 0; i < N; i++) { //현재 mid를 최대 길이로 설정하고 과자를 몇 조각으로 나누는지 계산한다.
			cnt += v[i] / mid;
		}
		if (cnt >= M) { //과자 조각이 조카의 수 이상이면
			ans = mid; //답으로 설정하고
			start = mid + 1; //작은 범위를 현재 mid + 1로 설정
		}
		else { //그 외의 경우
			stop = mid - 1; //큰 범위를 현재 mid - 1로 설정
		}
	}

	cout << ans;
}