2187. Minimum Time to Complete Trips

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

Minimum Time to Complete Trips - LeetCode

 

 

문제 해석부터 무슨 소리를 하는지 모르겠지만 보다 보니까 무슨 문제인지 이건 말로 풀어쓰는 거보다 직접 보고 이해하기를 어쨌든 중요한 건 주어진 버스 운행 횟수를 만족하기 위한 최소 시간 구하기

일단 시간이 주어지면 몇 번 운행 가능한지 리턴하는 함수를 하나 만든다 그리고 계속 반복함 찾을 때까지 물론 1부터 하나씩 늘려가는 멍청한 짓은 하면 안 되고 시간과 횟수는 비례하기 때문에 이진 탐색이 가능하다 적당히 큰 수 b 와 0부터 시작하는 a 두 변수로 중간 시간 넣고 2배로 줄이고 반복하다 보면 n 번 에서  log2(n)으로 시간 많이 줄어든다.

 

 

class Solution:
    def minimumTime(self, l: List[int], k: int) -> int:
        if len(l)==1:
            return(k*l[0])
        def f(x,t):
            s=0
            for i in t:
                if x<i:
                    return s
                s+=(x//i)*d[i]
            return s
        d={}
        for i in l:
            d.setdefault(i,0)
            d[i]+=1

        l=sorted(set(l))
        a=0
        b=1000000000000
        
        while True:
            c=(a+b)//2
            t=f(c,l)
            if t==k:
                i=1
                a=f(c-i,l)
                while a==k:
                    i+=1
                    a=f(c-i,l)
                return(c-i+1)
                break
            if b-a==1:
                if k>t:
                    return(c+1)
                else:
                    return(c)
                break
            if k<t:
                b=c
            else:
                a=c