프로그래머스 - 금과 은 운반하기

 

def solution(a, b, g, s, w, t):
    left = 0 # 최소 시간
    right = 10 **15 # 최대 시간, 10^15
    answer = right 
    
    while left <= right:
        mid = (left + right) // 2
        
        if is_possible (mid, a, b, g, s, w, t):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1    
    return answer

def is_possible(time, a, b, g, s, w, t):
    total_gold = 0
    total_silver = 0
    total_weight = 0
    
    for i in range(len(g)):
        round_trip = t[i] * 2 # 왕복 시간
        trips = time // round_trip # 주어진 시간 동안 가능한 왕복 횟수
        if time % round_trip >= t[i]: # 남은 시간이 걸리는 시간 보다 작을 경우, 편도로 1번 더 갈 수 있음
            trips += 1
        max_move = trips * w[i] # 총 운반 가능한 무게 
        moved_gold = min(g[i], max_move)
        moved_silver = min(s[i], max_move)
        
        moved_total = min(g[i]+s[i], max_move)
        
        total_gold += moved_gold
        total_silver += moved_silver
        total_weight += moved_total
        
    return total_gold >= a and total_silver >=b and total_weight >= (a+b)

---

 

* 이진 탐색이란 ?

정렬된 데이터에서 원하는 값을 빠르게 찾는 방법

 

1. 가운데 값을 확인

2. 원하는 값보다 작으면 오른쪽, 크면 왼쪽

3. 계속 반으로 나누며 찾는 방식

 

- 시간 같은 걸 이진 탐색시, 보통 left = 0, right = 큰 수 로 시작

- 조건을 만족하는 최소값/최대값을 찾을 시, mid 값에 조건을 넣어 True/False로 판단

 

## 이진 탐색 기본 코드 틀  

left = 최소값
right = 최대값
answer = 무슨 기준값 (보통 right)

while left <= right:
    mid = (left + right) // 2

    if 조건(mid):
        answer = mid        # 조건 만족하면 정답 후보 저장
        right = mid - 1     # 더 나은(작은) 정답을 찾기 위해 왼쪽으로
    else:
        left = mid + 1      # 조건 불만족이니 더 큰 값으로