백준 2792 - 보석 상자

문제 설명

보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.

한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.

상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, BBB로 보석을 나누어주면 질투심은 3이 되고, 이 값보다 작게 나누어 줄 수 없다.

상자 안의 보석 정보와 학생의 수가 주어졌을 때, 질투심이 최소가 되게 보석을 나누어주는 방법을 알아내는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, M종류의 보석을 N명에 사람에게 나누어 줄 때, 한 사람이 받은 보석이 가장 최소가 되게 하면 된다.

단, 한 사람은 여러 종류의 보석을 받을 수 없다.

 

해당 문제는 최적해를 구하는 문제이다.

하지만, 최적해를 구하기 위해서는 계산해야 할 조건이 많다.

여러 종류의 보석을 받을 수 없다는 점과 최소가 되게 하기 위해 가중치를 계산하는 등의 작업이 필요할 것이다.

 

하지만, 해당 문제를 다르게 접근해볼 수 있다.

최적해를 구하는 문제를 이진 탐색과 결정 문제로 바꿔볼 수 있다.

 

우선, 우리가 구하는 정답을 K라고 하자.

이는 한 사람이 받은 보석 중 최대 개수가 될 것이다.

 

K가 정해졌다면 모든 보석을 사람들에게 나눠준 상황을 쉽게 구할 수 있다.

모든 보석을 K로 나누어 보면 되기 때문이다.

이렇게 되면 K개씩 나눠줬을 때 모든 보석을 나눠주기 위해 필요한 사람의 수를 구할 수 있다.

이것이 N보다 작거나 같다면 보석을 K개씩 나눠줘도 된다는 뜻이다.

 

그렇다면 이제 K개를 정하는 방법만 알면 된다.

한 사람은 최대 M개의 보석 중 가장 많은 보석의 수만큼 받을 수 있다.

M <= N 이고 한 사람이 여러 종류의 보석을 받을 수 없기 때문이다.

그리고 최소는 0개일 것이다.

아무것도 받지 않는 사람이 존재할 수 있기 때문이다.

 

이제 최소, 최대 범위 안에서 이진 탐색을 통해 가능한 개수를 찾아보며 최솟값을 찾으면 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<long long> jewels;

bool check(long long mid)
{
	if (mid == 0) return false;

	int cnt = 0;
	for (auto jewel : jewels)
	{
		cnt += jewel / mid;
		if (jewel % mid != 0) cnt++;
	}

	return cnt <= N;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;

	cin >> N >> M;

	jewels.resize(M);

	long long left = 0;
	long long right = 0;

	for (int i = 0; i < M; i++)
	{
		cin >> jewels[i];
		right = max(right, jewels[i]);
	}

	long long ans = LLONG_MAX;
	while (left <= right)
	{
		long long mid = (left + right) / 2;

		if (check(mid))
		{
			ans = min(ans, mid);
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}

	cout << ans;


	return 0;
}

---