백준 16401 - 과자 나눠주기

문제 설명

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 N개의 과자를 M명의 조카에게 동일한 길이로 나눠주려 할 때 최대 길이를 구하면 된다.

 

처음 문제를 보면 정말 간단해 보인다.

정렬해서 M번째로 큰 수를 고르면 되지 않을까 생각할 수 있다.

하지만 이는 항상 최적해가 되지 않는다.

예를 들어 보자.

4 3
10 10 15

이러한 입력이 있다고 하면 4명에게 과자를 나눠 줘야 하기 때문에 과자 하나를 나눠야 한다.

또한 개수가 충분하더라도 가장 큰 과자가 다른 과자에 비해 월등하게 크다면 해당 과자를 나눠 M명에게 배분할 수 있으므로 여러 예외 상황이 발생한다.

 

이를 해결하는 방법은 최적해를 구하는 문제에서 판단 문제로 바꾸면 간단해진다.

길이가 k인 과자를 나눠줄 수 있는지 여부는 정말 간단하게 구할 수 있다.

모든 과자를 k로 나눠 몫의 합이 M보다 크거나 같으면 된다.

bool Check(int mid)
{
	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		cnt += snacks[i] / mid;
	}

	return M <= cnt;
}

 

이를 이분 탐색으로 최댓값을 구하면 된다.

int left = 1;
int right = snacks.back();

int ans = 0;
while (left <= right)
{
	int mid = (left + right) / 2;
	if (Check(mid))
	{
		left = mid + 1;
		ans = max(ans, mid);
	}
	else
	{
		right = mid - 1;
	}
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int M, N;
vector<int> snacks;

bool Check(int mid)
{
	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		cnt += snacks[i] / mid;
	}

	return M <= cnt;
}

int main()
{
	INPUT_OPTIMIZE;
	
	cin >> M >> N;
	snacks.resize(N);

	for (int i = 0; i < N; i++)
	{
		cin >> snacks[i];
	}

	sort(snacks.begin(), snacks.end());

	int left = 1;
	int right = snacks.back();

	int ans = 0;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (Check(mid))
		{
			left = mid + 1;
			ans = max(ans, mid);
		}
		else
		{
			right = mid - 1;
		}
	}

	cout << ans;

	return 0;
}

---