[Programmers] Q86503 금과 은 운반하기

[Programmers] Q86503 금과 은 운반하기

Question

Language: Python

주어진 문제의 입력 조건을 확인하면 2 * 10⁹ * 10⁵ 만큼의 시간이 소요되므로 O(logn)의 접근이 요구된다. 따라서, 시간에 대한 이분 탐색을 통해 문제를 풀이한다.

모든 도시에서 병렬적으로 금,은을 운반하는 것이 가능하므로 각각의 도시에 대해 운반 가능한 최대 금, 은, 총 운반량을 구해서, 주어진 조건에 만족하는지를 확인한다.

#아래의 조건이 성립하는 경우에 대해서 도시를 짓기 위한 광물 양을 맞출 수 있다.
if gold_sum >=a and silver_sum >=b and total_sum >=a+b:
    end=mid-1
    answer=mid

Solution

def solution(a, b, g, s, w, t):
    answer=-1
    start,end=0,10**16
    #최소 시간에 대한 경우를 구하는 경우 이므로 --> 시간이 많이 걸리는 경우 이분 탐색을 활용한다.
    while start <= end:
        mid=(start+end)//2
        
        gold_sum,silver_sum,total_sum=0,0,0
        
        for gold,silver,weight,time in zip(g,s,w,t):
            #최대 왕복 횟수
            moving_count=(mid // (2*time))
            #편도 추가
            if mid % (2*time) >= time:
                moving_count+=1
                
            #최대 이동 가능 중량
            available_total=moving_count * weight
            
            #금,은,최대 이동 중량 에 대한 조사
            gold_sum += min(available_total,gold)
            silver_sum += min(available_total,silver)
            total_sum += min(available_total,gold+silver)

        #a 이상 금, b이상의 금, 총 중량이 a+b를 초과하므로 해당 시간 내에 이동하는 것이 가능하다.
        if gold_sum >=a and silver_sum >=b and total_sum >=a+b:
            end=mid-1
            answer=mid
        else:
            start=mid+1
            
       
    return answer