BOJ-14627 파닭파닭

필요한 지식

1. 이분탐색

접근

1. 이분탐색의 mid값을 파닭에 넣을수 있는 최대 파의 길이로 정의하고 진행한다.

2. 입력받을때 파의 길이 중 최대값을 저장해 두고, mid값이 저장한 최대값 보다 크다면 right를 mid-1로 바꿔주고 다음단계로 진행한다.

3. 2번 조건을 만족하는 경우 모든 파의 길이를 봐주면서 현재 mid값으로 사용가능한 파의 개수를 구해주고 그 개수가 문제에서 주어진 C개 보다 크다면 ans변수에 sum-c*mid값(최소의 파를 사용하고 나서 남은 파의 길이)을 업데이트 시켜준다.

코드(C++)

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<ll>v;
ll maxval = 0, sum = 0, ans = LLONG_MAX;
int main() {
	ll s, c; cin >> s >> c;
	for (int i = 0; i < s; i++) {
		ll x; cin >> x; v.push_back(x);
		maxval = max(maxval, x);
		sum += x;
	}
	ll l = 0, r = LLONG_MAX;
	while (l <= r) {
		ll mid = (l + r) / 2;
		ll cnt = 0;
		if (maxval < mid) {
			r = mid - 1;
			continue;
		}
		for (auto it : v) {
			cnt += it / mid;
		}
		if (cnt >= c) ans = min(ans, sum - c * mid);
		if (cnt < c) {
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	cout << ans;
	return 0;
}