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

 

 

문제 16401번

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

 

left와 right에 각각 과자의 최소 길이와 최대 길이를 넣어준다. 그리고 그것들의 사이의 길이인 mid를 이용한다.
과자의 길이들을 담은 L배열에 현재 기준으로 잡은 길이인 mid를 나눠 나온 수를 count에 더해준다. 해당 count는 mid의 길이로 몇명에게 나눠줄 수 있는지 보기 위해 count하는 것이다.
몇명나눠줬는지 확인한 count가 조카 수보다 크거나 같다면 과자가 짧아 길이가 더 길어져도 된다는 소리이기 때문에 left의 위치를 mid+1로 옮겨준다.
그리고 나눠줄 수 있는 과자의 최대길이를 저장하는 result변수에 현재 과자의 길이인 mid를 넣어준다(계속 반복하다보면 최대길이가 저장됨).
count가 조카 수보다 작다면 과자가 길어 나눠줄 수 없다는 소리이기 때문에 right의 위치를 mid-1로 옮겨준다.
그리고 그렇게 나온 result값을 출력해주면 된다.

 

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

int main() {
	int M, N;
	cin >> M >> N;
	int* L = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> L[i];
	}
	sort(L, L + N);
	int result = 0;
	int left = 1, right = L[N - 1];
	while (left <= right) {
		int mid = (left + right) / 2;
		int count = 0;
		for (int i = 0; i < N; i++) {
			count += L[i] / mid;
		}

		if (count >= M) {
			left = mid + 1;
			result = mid;
		}
		else if (count < M) {
			right = mid - 1;
		}

	}
	cout << result;

	return 0;
}