접근

  1. 가능한 속도 1 과 10^7 사이에서 binary search 로 최소 속도를 찾는다.
  2. 각 속도마다 train list 를 돌며 걸리는 시간을 계산에서 binary search range 를 조정한다.
  3. 시간복잡도 O(Nlog10^7)

사고

적정값을 찾아야 되는 문제는 binary search 로 접근하는 경우가 많은거같다. 무난한 binary search 유형이다.

 

import math
class Solution:
    def minSpeedOnTime(self, dist: list[int], hour: float) -> int:
        lo, hi = 1, 10000000
        minspeed = float('inf')
        while hi >= lo:
            mid = (hi + lo) // 2
            timetook = 0
            for i in range(len(dist) - 1):
                timetook += math.ceil(dist[i] / mid)
            timetook += dist[-1] / mid
            if timetook <= hour:
                minspeed = mid
                hi = mid - 1
            else:
                lo = mid + 1

        if minspeed == float('inf'):
            return -1
        else:
            return minspeed

submission