[백준 18113번 / C++] 그르다 김가놈

이분 탐색 문제이다. 

 

접근 방식

 

1. 벡터 V에 꼬다리를 조건에 맞게 제거한 김밥 길이를 저장한다. 

 - 김밥 길이가 2kcm 짧으면 한쪽만 꼬다리 짜름 

 - 김밥 길이가 kcm이거나 그보다 짧으면 김밥 폐기 

 - 위의 조건에 해당되지 않으면 두쪽 꼬다리를 자름 

 

2. p(mid) 의 최댓값을 구하기 위해서 low 값이 갱신될 때 result 값에 mid값을 넣어준다. 

 

3. p의 값이 존재하지 않을 경우 - 1을 출력한다. 

#include <iostream>
#include <vector>
using namespace std; 
typedef long long ll; 
int main() {
	//꼬다리 잘라낸 김밥 -> 손질된 김밥
	//김밥 N개, kcm 잘라낸다 양쪽 균일하게
	//김밥 길이가 2kcm 짧으면 한쪽만 꼬다리 짜름 
	// 김밥 길이가 kcm이거나 그보다 짧으면 김밥 폐기 
	// 손질된 김밥을 모두 일정한 p로 잘라서 pcm 김밥 조각 만들기 
	// p를 최대한 길게 low 부분에서 mid 값 저장 
	ios::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0); 
	int n, k, m; //최소 m개 	
	cin >> n >> k >> m; 
	vector <int> v; 
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		if (a <= k)a = 0;
		else if (a < 2 * k)a -= k;
		else a -= 2 * k; 
		v.push_back(a); 
	}
	int l = 1; int h = 1000000000; 
	int result = -1; 
	while (l <= h) {
		int mid = (l + h) / 2; 
		int cnt = 0; 
		for (int i = 0; i < n; i++) {
			cnt += v[i] / mid; 
		}
		if (m > cnt) {
			h = mid - 1; 
		}
		else {
			result = mid; 
			l = mid + 1; 
		}
	}
	cout << result; 	
}

18113번: 그르다 김가놈