[ Lv 3 ] [ 이분 탐색 ] 금과 은 운반하기

https://programmers.co.kr/learn/courses/30/lessons/86053?language=python3 

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

 

---

풀이 과정

---

1. 걸리는 시간의 범위가 크기 때문에 전체 범위가 너무 커질것 같아 이분탐색을 고려하였으나 이분 탐색 시 시뮬레이션 하는 파트 생각이 안나서 게시된 문제 풀이를 참조함.
2. 현재 시간을 t분이라고 할 때
   1. t분동안 물건을 나르는 횟수는 크게 mid // (걸리는 시간 * 2)이고, 맨 마지막에 편도로 이동 가능하므로 mid % (걸리는 시간 * 2)가 걸리는 시간보다 큰 경우는 횟수를 하나 늘려준다.
   2. t분동안 각각의 도시에서 옮길 수 있는 최대 금, 최대 은 개수를 각각 더해준다.
   3. 동시에 각각의 도시에서 옮길 수 있는 광물의 수의 총합도 구해준다.
   4. 다음 조건이 만족하면 정답을 저장하고 왼쪽 구간을, 아니라면 오른쪽 구간을 진행한다.
      1. 옮길수 있는 최대 금의 개수가 a보다 큰지
      2. 옮길수 있는 최대 은의 개수가 b보다 큰지
      3. 각각의 도시에서 옮길수 있는 광물의 수의 합이 a+b보다 큰지
   5. 잘 생각해 보면, 옮길 수 있는 광물의 수의 합이 a+b보다 크고, 최대 금과 최대 은의 개수가 a, b보다 크다면 금과 은의 개수를 적절하게 맞추어 준다면 금 a kg 이상, 은 b kg 이상을 나를 수 있다.
3. 시뮬레이션 파트를 잘 생각하지 못해서 풀지 못했던 문제임.. 고민 많이 해볼것.

---

소스 코드

---

def solution(a, b, g, s, w, t):
    answer = int(10**16)
    left, right = 0, int(10**16)
    
    while left <= right:
        mid = (left + right) // 2
        gold = 0
        silver = 0
        total = 0
        for i in range(len(g)):
            movement_count = mid // (t[i] * 2)
            if mid % (t[i] * 2) >= t[i]:
                movement_count += 1
            city_gold = w[i] * movement_count if w[i] * movement_count <= g[i] else g[i]
            city_silver = w[i] * movement_count if w[i] * movement_count <= s[i] else s[i]
            gold += city_gold
            silver += city_silver
            total += w[i] * movement_count if s[i] + g[i] >= w[i] * movement_count else s[i] + g[i]

        if gold >= a and silver >= b and total >= a + b:
            right = mid - 1
            answer = min(answer, mid)
        else:
            left = mid + 1
        
    return answer