개발/알고리즘

백준 14627번 파닭파닭 C++

daisy-day 2021. 4. 4. 01:42

문제

www.acmicpc.net/problem/14627

 

14627번: 파닭파닭

첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1≤S≤1,000,000), 그리고 주문받은 파닭의 수 C(1≤C≤1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S≤C) 그 후, S 줄에 걸쳐 파

www.acmicpc.net

코드

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
ll s, c, cnt, sum, arr[1000000];

bool check(ll mid)
{
	ll quotient = 0;
	for (int i = 0; i < s; i++)
		quotient += arr[i] / mid;

	return quotient < c;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> s >> c;
	ll low = 1, high = 0;
	for (int i = 0; i < s; i++)
	{
		cin >> arr[i];
		sum += arr[i];
		high = max(high, arr[i]);
	}

	while (low <= high)
	{
		ll mid = (low + high) / (1LL * 2);
		if (check(mid))
		{
			high = mid - 1;
		}
		else
		{
			low = mid + 1;
			cnt = mid;
		}
	}

	cout << sum - (cnt * c) << "\n";
	return 0;
}