- 문제 링크: leetcode.com/problems/koko-eating-bananas/

 

이분탐색 문제입니다. 백준에서 랜선 자르기인가 그 문제랑 비슷하죠?

별로 어렵지는 않습니다... 근데 문제는 이분탐색은 항상 짤때마다 헷갈립니다.

저는 아예 이분탐색 포맷을 외워놨습니다.

while (l<=r) { mid = (l+r)/2; if(fun()) r=mid-1; else l=mid+1; } 이렇게 한 다음에 마지막 r이 조건을 불만족하는 마지막 값? 이라고 생각하시면 되겠습니다. 그러니 답은 r+1인거죠

뭐 그렇습니다..

class Solution(object):
    def minEatingSpeed(self, piles, H):
        """
        :type piles: List[int]
        :type H: int
        :rtype: int
        """
        l = 1
        r = max(piles)
        while l <= r:
            mid = (l + r) // 2
            h_need = sum(((i-1)//mid)+1 for i in piles)

            if h_need <= H:  # ok
                r = mid - 1
            else:
                l = mid + 1
        return r+1

 

반응형