[백준 14627번 / C++] 파닭파닭

1. 범위가 "1<= L <=1,000,000,000" 라면 이진탐색을 의심하자. 이진탐색으로 구현. 

2. 각 파의 길이 값을 벡터에 저장. 

3. 공통된 길이의 파를 구할 때까지 이진탐색

• 각 파의 길이 값을 갖고 있는 벡터의 원소마다 이진 탐색으로 얻게된 mid값을 나누어서 얻는 몫의 합이 C와 같아야한다. 
• 최댓값을 구할땐 low값을 변경하는 조건문에서 mid값 저장해놓기 (최솟값일 땐 high 조건문)  

 

4. 나머지 계산 

#include <iostream>
#include <vector>
using namespace std; 
int a, b;
vector <int> v;
typedef long long ll; 
bool check(ll mid) {
	ll cnt = 0; 
	for (int i = 0; i < v.size(); i++) {
		cnt += v[i] / mid; 
	}
	return cnt >= b; 
}
int main() {
	cin >> a >> b; 
	v.resize(a, 0); 
	ll sum = 0; 
	for (int i = 0; i < a; i++) {
		cin >> v[i]; sum += v[i]; 
	}
	ll l = 1; 
	ll h = 1000000000; 
	ll result = 0; 
	while (l <= h) {
		ll mid = (l + h) / 2; 
	    //최대를 묻는 문제 
		if (check(mid)) {			
			l = mid + 1;
			result = mid; 
		}
		else {
			h = mid - 1;
		}
	}
	ll ans = sum-result*b; 
	cout << ans; 
}

14627번: 파닭파닭