Leetcode 1870. Minimum Speed to Arrive on Time

https://leetcode.com/problems/minimum-speed-to-arrive-on-time/description/

Minimum Speed to Arrive on Time - LeetCode

 

문제

 

부동소수점인 숫자 hour가 주어진다. 이 hour안에 반드시 사무실에 도착해야 한다. 사무실을 가기 위해서는 n개의 기차를 순서대로 타야한다. dist 배열이 주어지며 dist[i]는 i번째 열차의 거리를 나타낸다.

 

각 열차는 정수의 시간에 출발하며 열차를 타기 위해서 기다려야할 수도 있다.

 

• 예를 들어, 첫번째 열차가 1.5시간이 걸린다면 두번째 열차는 정수시간에 출발하므로 0.5시간을 기다려야 한다.

위의 조건을 바탕으로 양수인 최소 스피드를 구하여 반환하여라. 만약 위의 조건을 만족하지 못한다면 -1을 반환하라

 

모든 테스트케이스의 속도는 10의 7승을 넘지 않는다. 또한 hour는 소수점 2째자리 까지 표현된다.

 

코드

from math import ceil

class Solution:

    def minSpeedOnTime(self, dist: list[int], hour: float) -> int:

        def hours(speed):

            return sum(map(lambda x: ceil(x / speed), dist[:-1])) + dist[-1] / speed

        i = 1; j = 10 ** 7 + 1

        answer = -1

        while i < j:

            s = (i + j) // 2

           

            if hours(s) <= hour:

                answer = s

                j = s

            else:

                i = s + 1

        return answer

---

바이너리 서치를 이용한 문제, 바이너리 서치를 하기위해서 범위를 지정하는게 제일 어려운거 같다