[릿코드 2187] Minimum Time to Complete Trips (파이썬/python)

https://leetcode.com/problems/minimum-time-to-complete-trips/description/

Minimum Time to Complete Trips - LeetCode

 

모든 totalTrips 를 충족하는 minimum time 을 계산하는 문제였습니다.

시간을 이진탐색의 값을 설정하여

반복문을 돌며 이진탐색을 하여

 

totalTrips 를 충족하는 시간을 리턴하면 됩니다.

조건상 input 의 크기가 꽤 커서 완전탐색만으로는 시간안에 풀 수 없습니다.

 

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        # 시간을 기준으로 이분탐색
        # max 인 시간은 가장 작은 값으로 혼자 여러번뛰었을때 totalTrips 이 되는 때이다.
        start, end = 1, totalTrips * min(time)

        while start <= end:
            mid = (start + end) // 2

            total_cnt = 0
            for t in time:
                if t <= mid:
                    total_cnt += mid // t

            if total_cnt >= totalTrips:
                end = mid - 1
            else:
                start = mid + 1

        return end