[프로그래머스] 금과 은 운반하기 (이분 탐색)

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

프로그래머스

 

분석

최솟값(0)과 최댓값(가장 오래 걸리는 도시 트럭으로 금과 은 전체 운반) 사이를 이분 탐색을 통해 최적값 찾아내기

a : 필요한 금의 무게
b : 필요한 은의 무게
g : 각 도시의 금의 양
s : 각 도시의 은의 양
w : 각 도시의 트럭이 운반할 수 있는 최대 무게
t : 도시에서 이동하는 편도 시간

a	b	g	s	w	t	result
90	50	[70, 70, 0]	[0, 0, 500]	[100, 100, 2]	[4, 8, 1]	499

l	r	time	gold	sirver	weight
0	9440	4720	140	500	640
0	4720	2360	140	500	640
0	2360	1180	140	500	640
0	1180	590	140	500	640
0	590	295	140	500	640
296	590	443	140	500	584
444	590	517	140	500	584
444	517	480	140	480	620
481	517	499	140	500	640
481	499	490	140	490	630
496	499	497	140	498	638
498	499	498	140	498	636

 

2023.05.25 - [BOJ/Search] - [1654] 랜선 자르기(이분탐색, 결정 알고리즘)

[1654] 랜선 자르기(이분탐색, 결정 알고리즘)

 

 

풀이

from math import ceil, floor
def solution(a, b, g, s, w, t):
    answer = -1
    
    def count(time):
        gold=0
        silver=0
        weight=0
        
        for i in range(len(g)):
            tmp=floor(time/t[i])
            deliver=tmp//2+tmp%2
            
            gold+=min(g[i], w[i]*deliver) # 가지고 있는 골드, 트럭 용량 작은 값
            silver+=min(s[i], w[i]*deliver) # 가지고 있는 실버, 트럭 용량 작은 값
            weight+=min(g[i]+s[i], w[i]*deliver) 
            
        if gold>=a and silver>=b and weight>=a+b:
            return True
        else:
            return False
    
    l=0
    r=(a+b)*max(t)*2
    while l<r:
        print(l,r)
        mid=(l+r)//2
        if count(mid):
            answer=mid
            r=mid
        else:
            l=mid+1
    
    return answer