[프로그래머스][level3] 금과 은 운반하기 - python / 파라메트릭 서치

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/86053

코딩테스트 연습 - 금과 은 운반하기

 

풀이 

- 파라메트릭 서치(Parametric Search)

: 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘

: 조건을 만족하는 최댓값이나, 최솟값을 구하는 등의 최적화 문제를 결정 문제로 바꾸어 푸는 것

- 이진 탐색(Binary Search)

: 정렬된 일련의 값들이 주어졌을 때 그 값들 중에서 원하는 값을 찾는 알고리즘 

 

-  파라메트릭 서치 알고리즘 사용하는 문제

: 트럭을 최적으로 운행하여 금과 은을 전달할 수 있는 가장 빠른 시간을 이분 탐색을 통해 구하는 문제 

 

1. 이분 탐색의 시작 최솟값은 0

최댓값은 (도시 개수 최댓값) * (편도 이동 시간 최댓값) * 2 (왕복이므로) * 2 (금과 은이 모두 따로 있을 때) 

이므로 10**16 으로 설정

 

2. 시간 내에 

각 도시별 옮길 수 있는 최대 금과 은의 개수를 구한다.

각 도시별 옮길 수 있는 최대 광물의 개수를 구한다. 

 

시간 내에 옮길 수 있는 최대 금과 은, 광물들의 개수의 합을 각각 구한다.

 

3. 옮길 수 있는 최대 금의 개수가 옮겨야 하는 금의 개수보다 크거나 같고, 

옮길 수 있는 최대 은의 개수가 옮겨야 하는 은의 개수보다 크거나 같고, 

옮길 수 있는 최대 광물의 개수가 옮겨야 하는 광물의 개수보다 크거나 같으면 

최소 시간 갱신 후, 시간 줄이기 

 

그렇지 않으면 

시간 늘리기 

def solution(a, b, g, s, w, t):
    answer = int(10**16)
    left = 0 
    right = int(10**16)
    
    while left <= right :
        mid = (left + right) // 2 
        gold = 0 
        silver = 0 
        total = 0 
        
        # 각 도시 별 
        for i in range(len(g)):
            # 왕복할 수 있는 최대 횟수 
            cnt = mid // (t[i] * 2)
            # 편도로 이동가능하면 + 1 
            if mid % ( t[i] * 2 ) >= t[i]:
                cnt += 1 
            
            c_gold = 0
            c_silver = 0
            # 옮길 수 있는 최대 금과 은 구하기 
            if w[i] * cnt <= g[i] :
                c_gold = w[i] * cnt 
            else:
                c_gold = g[i]
                
            if w[i] * cnt <= s[i]:
                c_silver =  w[i] * cnt 
            else:
                c_silver = s[i]
        
            # 도시에서 옮길 수 있는 광물의 총합의 최댓값 구하기 
            if w[i] * cnt <= s[i] + g[i] :
                total += w[i] * cnt 
            else:
                total += s[i] + g[i]
            
            # 옮길 수 있는 금과 은의 총합     
            gold += c_gold 
            silver += c_silver
            
        # 옮길 수 있는 최대 금의 개수가 옮겨야하는 금의 개수보다 크면 
        # 옮길 수 있는 최대 은의 개수가 옮겨야하는 은의 개수보다 크면 
        # 옮길 수 있는 최대 광물의 개수가 옮겨야하는 광물의 개수보다 크면     
        if gold >= a and silver >= b and total >= a+b:
            # 최소 시간 갱신 
            answer = min(answer,mid)
            right = mid -1
        else:
            left = mid + 1 
            
    return answer

 

- 금과 은 둘 중에 하나라도 옮길 수 있다면 늘리기