백준, boj) 2792. 보석상자 ( C/ C++)

1. 문제 링크

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

2792번: 보석 상자

2. 문제 개요

모든 보석을 N명의 학생들에게 나누어 주려고 한다. 가장 많이 가져간 아이의 보석의 수가 질투심이라고 할 때, 질투심을 최소하 하라.

 

3. 문제 힌트

 말이 질투심이니 뭐니 해서 그렇지 결국 아이들이 조건을 만족하면서 질투심을 가장 작게 만드는 방법을 찾는것이다.

질투심을 X라고 가정하고 조건을 만족하는지 체크하고 이분 탐색하기.

 

4. 문제 풀이

조건을 만족하면 값을 저장하고 최솟값을 찾아야 하므로 right를 mid-1로 조정한다.

조건을 만족하지 못하면 질투심을 높여야 하므로 left를 mid+1 한다.

 

5. 코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

vector<int> v;

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	v.resize(m);
	for (int i = 0; i < m; ++i)
		scanf("%d", &v[i]);

	int left = 1, right = 1e9;
	int ans = 0;
	while (left <= right)
	{
		int mid = (left + right) / 2;

		//check
		int len = v.size();
		long long int sum = 0;

		for (int i = 0; i < len; ++i)
		{
			sum += (long long int)ceil((double)v[i] / (double)mid);
		}
		if (sum <= n)
		{
			right = mid - 1;
			ans = mid;
		}
		else
		{
			left = mid + 1;
		}
	}
	printf("%d", ans);

	return 0;
}

6. 결과 사진

 

 

지적, 댓글 언제나 환영입니다~