[LeetCode] 875. Koko Eating Bananas

문제 URL : https://leetcode.com/problems/koko-eating-bananas/description/

Koko Eating Bananas - LeetCode

 

문제 접근법 : 

이분탐색을 요구하는 문제입니다.

배열안에 piles[i]개의 바나가가 있는데 코코라는 애가

입만드럽게커서 1시간마다 x개를 먹을수있다고하네요

그러나 piles[i]가  x개보다 작아도 1시간 동안 그양만먹고 쉰다음 그다음것을 먹게된다고할때

 

h시간후에 관리자가 오기전에 piles안에있는것을 다처먹으려고할때 코코의 주둥아리에 들어가는 바나나를

좀 최소화 하고싶다고합니다.

최소화할때의 그x를 구하면됩니다.

 

정말 간단하게 생각하면 x가 1부터시작해서  1씩증가하면

piles = [3,6 ,7, 11]  , h=8일때 1시간당 1개씩처먹으면  3+6+7+11  =27 > h를 초과해버립니다.

즉다먹못먹으니 좀더 크게 잡아야겠쬬 2개씩 처먹는다면 (3/2)+1 +  (6/2) + (7/2)+1,(11/2)+1 = 16>h

더못먹으니 좀더 크게잡아야하고

3개씩 먹는다해도 안되고

4개씩 먹는다면 1+2+2+3 =8 이고 h=8 시간내에 다먹으니 4가 됩니다.

 

즉이렇게 1씩 증가하면 당연히 시간초과가날테니

이분탐색으로 크게잡아 다먹을수있는 입크기를 확인하면서 h이하가 되는경우중 가장작은 x값을 구하면됩니다.

 

소스코드 :

 

class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
	int res =1e8;
	long long l=1,r=1e15;
	while(l<=r){
		long long mid = (l+r)/2;
		long long sum=0;
		for(int i : piles){
			sum+=i/mid;
			if(i%mid)sum++;
		}
		if(sum<=h){
			r=mid-1;
			res=mid;
		}
		else{
			l=mid+1;
		}
	}
	return res;
}
};

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.