[Binary Search][Medium] 875. Koko Eating Bananas

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

Koko Eating Bananas - LeetCode

 

Q. 주어진 vector piles는 각 바나나 개수를 의미한다. 원숭이가 h시간내에 먹을 수 있는 최소의 시간당 먹을 수 있는 바나나의 개수를 구하라. 

  이때 piles의 바나나 수가 시간 내 먹을 수 있는 수 보다 적으면, 그 시간엔 그 piles만 먹고 더 먹지 않는다.

 

 

Solution. 

  문제 자체보다 해석에 공이 들어가는 문제다. 

 

 원숭이가 특정 시간 내에 바나나를 시간당 먹을 수 있는 최소의 수를 찾아라. 

 좀 복잡하게 들린다. 

 

 정리 해 보자. 

  2, 3, 4 의 더미가 있을때 

  원숭이가 시간당 2개씩 먹을 수 있다면, 

   1 2 2 해서 총 5시간이 걸린다. 

 

  시간당 4개씩 먹을 수 있다면, 

  1, 1, 1 해서 총 3시간이 걸린다. 

 

 문제에서는 이 총 시간이 주어지고, 이 시간을 만족하는 시간당 바나나수 중 가장 작은 수를 찾으라는 것이다. 

  다시 보자. 

 

 h가 5라면, 

 원숭이가 2개씩 먹으면, 위에서와 같이 1, 2, 2로 총 5를 만족한다. 

  4개씩 먹어도 총 3시간으로 총 5시간 내에 먹는 것을 만족한다. 

  따라서, 특정 만족하는 수가 생기면 그 뒤로는 모두 만족하게 되므로, 

  이 최소값을 구하라는 것이다. (음...)

 

 

아무튼 이 문제는 시도하는 수에 집중한다.

 

 어떤 수를 시도 할 것인가, 

 우선 최대 바나나 더미 만큼 먹으면 배열 수의 시간 내에 무조건 다 먹을 수 있게 될 것이다. 

즉, [2, 3, 4] 에서 원숭이가 4로 먹으면, 1, 1, 1 해서 3시간이 걸린다. 

 4보다 더 많이 먹어도, 조건 상(바나나가 남아도 해당 시간에는 해당 더미만 먹을 수 있다) 3시간은 무조건 걸린다. 

 따라서 4보다 더 큰 수를 시도할 필요는 없다.  

 

 반대로 보면, 1보다 작은 수를 시도할 필요는 없다. 

 

 그럼 특정 시도 수치를 만족하면 해당 방향 모두 만족하는가? 

 -> 1 -> max( 여기서는 4)로 시도하므로, 위의 특성도 모두 만족한다. 

 그럼 binary search가 우선은 적당해 보인다. 

 

 

 int koko_help(vector<int>& nums, long left, long right, int h)
{
    if (left > right) 
    	return left;

    long mid = left + (right - left) / 2;

    // 합산 시간의 범위가 충분히 커야 한다.
    long long totalTime = 0;
    for (int q = 0; q < nums.size(); ++q)
        totalTime += (nums[q] % mid) == 0 ? ((long)nums[q])/mid : 1 + (((long)nums[q])/mid);

    // 시도한 시간이 더 크다면, 현재 먹는 바나나 수가 작다는 것이므로, 수를 늘린다.
    if (totalTime > h)
        return koko_help(nums, mid + 1, right, h); 

    // 시도한 시간이 작거나 같다면, 현재 먹는 수가 적당하거나, 더 줄여야 한다는 것.
    // min 값을 찾아야 하므로, 이 방향으로 만족하지 않을때까지 간다.
    return koko_help(nums, left, mid - 1, h);
}

int minEatingSpeed(vector<int>& piles, int h) 
{
    long maxV = 0;
    for (int q = 0; q < piles.size(); ++q)
        maxV = max((int)maxV, piles[q]);

    return koko_help(piles, 1, maxV, h);
}

 

 

음....