[LeetCode] 875. Koko Eating Bananas

https://leetcode.com/problems/koko-eating-bananas/

Koko Eating Bananas - LeetCode

Koko Eating Bananas - Medium

 

경비가 h시간동안 자리를 비울때, 코코는 바나나 무더기에 있는 바나나를 모두 먹으려고 한다.

코코는 한 시간동안 한 무더기에서 k개의 바나나를 먹을 수 있다.

만약 해당 무더기의 바나나 수가 k보다 작더라도, 그 시간 동안은 해당 무더기에만 머물러야 한다.

이 때, 코코가 h시간안에 모든 바나나를 먹기 위한 k의 최소값을 구하는 문제다.

 

코코가 바나나를 먹는 k는 최소 1(l), 최대 10^9(r) 개다. (제한 조건에서 각 무더기에 있는 바나나의 최소, 최대값)

이를 binary search로 훑어주자.

이 경우 최대 log_2(10^9) = 9*log_2(10) = 9*3.XX 의 연산만 필요하므로 시간걱정은 없다.

각각의 값을 각 무더기에 있는 (바나나 수-1)에서 나눠주고 1을 다시 더해주면 해당 무더기에서 머무는 시간이 된다.

이 시간을 다 더했을때,

1) h 이하가 되면 이를 저장해주고, r을 mid - 1로 갱신.

2) h 보다 크다면 l을 mid + 1로 갱신.

그리고 l<=r 인 동안은 binary search를 반복하자.

 

전체 풀이 코드

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int l=1, r=1e9,m, s=0, ret=INT_MAX;
        while (l<=r) {
            m = (l+r)/2;
            s=0;
            for (int pile:piles) s+=((pile-1)/m)+1;
            if (s<=h) ret = m, r=m-1;
            else l=m+1;
        }
        return ret;
    }
};