금과 은 운반하기

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

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

 

블로그에서 다룬 적 있다. 

https://comdoc.tistory.com/entry/32-%EC%9D%B4%EC%A7%84-%EA%B2%80%EC%83%89Binary-Search

32. 이진 검색(Binary Search), 파이썬

주어진 시간 내에 도시 건설에 필요한 금과 은을 배송할 수 있는가?
라고 문제를 바꾸고 이분 검색을 쓰자... 

def solution(n_gold, n_silver, golds, silvers, weights, times):
    def deliver(time_limit):
        gold = silver = total = 0
        for i in range(len(golds)):
            # 편도 횟수
            one_way = time_limit // times[i]
            # 배달 횟수 = 왕복당 1회 + 1이 남으면 1 추가
            deliver_num = one_way // 2 + one_way % 2
            # 총 배송 가능 무게
            weight = deliver_num * weights[i]
            # 금만 보냈을 때 배송 가능한 금
            gold += min(golds[i], weight)
            # 은만 보냈을 때 배송 가능한 은
            silver += min(silvers[i], weight)
            # 배송 가능한 금과 은 모두!
            total += min(golds[i] + silvers[i], weight)
            # 금, 은, 모두가 배송 가능하면 True
        return gold >= n_gold and silver >= n_silver and total >= n_gold + n_silver

    end = answer = 10 ** 15
    start = 0
    while start <= end:
        mid = (start + end) // 2
        if deliver(mid):
            end = mid - 1
            answer = mid
        else:
            start = mid + 1
    return answer

필요한(needed, necessary) 이라는 의미로 변수명에 n을 사용했다. 
금, 은, 금과 은 모두가 배송가능해야 한다는 부분의 코드는 잘 떠오르지 않아서 다른 코드를 참고했다. 

테스트 1 〉	통과 (0.06ms, 10.3MB)
테스트 2 〉	통과 (0.06ms, 10.3MB)
테스트 3 〉	통과 (0.09ms, 10.3MB)
테스트 4 〉	통과 (0.11ms, 10.4MB)
테스트 5 〉	통과 (0.29ms, 10.3MB)
테스트 6 〉	통과 (0.51ms, 10.3MB)
테스트 7 〉	통과 (0.80ms, 10.3MB)
테스트 8 〉	통과 (2.40ms, 10.4MB)
테스트 9 〉	통과 (5.34ms, 10.3MB)
테스트 10 〉	통과 (8.96ms, 10.2MB)
테스트 11 〉	통과 (298.46ms, 11.3MB)
테스트 12 〉	통과 (662.78ms, 12.7MB)
테스트 13 〉	통과 (783.25ms, 13.7MB)
테스트 14 〉	통과 (1245.93ms, 15.1MB)
테스트 15 〉	통과 (1713.49ms, 16.4MB)
테스트 16 〉	통과 (1955.72ms, 17.8MB)
테스트 17 〉	통과 (2802.68ms, 21.3MB)
테스트 18 〉	통과 (3164.74ms, 22.4MB)
테스트 19 〉	통과 (2886.98ms, 22.4MB)
테스트 20 〉	통과 (2922.81ms, 22.3MB)
테스트 21 〉	통과 (2322.53ms, 22.3MB)
테스트 22 〉	통과 (2970.54ms, 22.3MB)
테스트 23 〉	통과 (2634.21ms, 22.3MB)
테스트 24 〉	통과 (0.10ms, 10.3MB)

프로그래머스 공식 블로그에 해설이 잘 나와 있다..
https://prgms.tistory.com/101