[백준] 18113번 - 그르다 김가놈 (C++) 문제 및 풀이

문제) 백준 - 이분 탐색 - 그르다 김가놈

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

18113번: 그르다 김가놈

 

N개의 김밥을 입력받아 꼬다리를 제외한 김밥 길이를 계산합니다. 김밥이 폐기되거나 길이가 0인 김밥은 필요가 없기 때문에 vector을 이용하여 김밥의 길이를 저장합니다. 이분 탐색을 이용하여 가능한 P의 최대를 계산합니다. 

 

C++ 소스 코드)

	#include<bits/stdc++.h>
	#define endl "\n"
	#define MAX 1000001
	#define INF 987654321
	#define ll long long
	using namespace std;
	typedef pair<int, int> p;
	int N, K, M;
	vector<int> rice;
	int solve(int P) {
	int ret = 0;
	for (int i = 0; i < rice.size(); ++i)
	ret += rice[i] / P;
	return ret;
	}
	signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N >> K >> M;
	int s = 0, e = 0;
	for (int i = 0; i < N; ++i) {
	int a; cin >> a;
	if (a >= 2 * K) {
	a -= 2 * K;
	}
	else if (a > K) {
	a -= K;
	}
	else
	a = 0;
	e = max(e, a);
	if (a > 0)
	rice.push_back(a);
	}
	int ans = -1;
	int mid;
	while (s <= e) {
	mid = (s + e) / 2;
	// Div by Zero
	if (mid == 0) {
	s++;
	continue;
	}
	if (solve(mid) >= M) {
	ans = max(mid, ans);
	s = mid + 1;
	}
	else {
	e = mid - 1;
	}
	}
	cout << ans;
	return 0;
	}

view raw 18113.cpp hosted with ❤ by GitHub