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

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

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

 

월간 코드 챌린지 시즌3 문제로 프로그래머스 Level 3에 올라와 있다.

https://prgms.tistory.com/101

월간 코드 챌린지 시즌3 9월 해설

 

위의 해설을 참고하여 이분탐색으로 풀었다.

제한사항으로 봤을 때 a=10**9, b=10**9, g=[10**9], s=[10**9], w=[1], t=[10**5] 라 했을 때 가장 큰 시간이 걸릴 것이므로 end 를 약 10^15 로 잡으면 되겠다.

 

위의 해설을 참고하면 아래와 같이 풀 수 있는데,

a <= gM and b <= sM and a + b <= (gM + sm or sM + gm) (gM + sm = sM + gm) 일 때, 금 akg, 은 bkg 를 운반할 수 있는 이유에 대해서 간단히 말하자면

금을 akg 이상 운반할 수 있으면 그 아래의 무게는 전부 운반할 수 있다. 은도 마찬가지이다.

(a + b)kg 이상을 운반할 수 있다고 하면, 금은 akg 운반할 수 있으므로 akg만 운반하고 나머지는 다 은을 운반하는데 투자한다고 했을 때, 은 또한 bkg 이상을 운반할 수 있는 조건이 되기 때문에 bkg의 은을 운반할 수 있다.

 

def solution(a, b, g, s, w, t):
    answer = float('inf')
    start = 0
    end = 10**9 * 10**5 * 4 - 10**5

    while start <= end:
        mid = (start + end) // 2
        gM, gm, sM, sm = 0, 0, 0, 0
        
        for i in range(len(t)):
            c = (mid - t[i]) // (2 * t[i]) + 1
            gM += g[i] if g[i] - c * w[i] <= 0 else c * w[i]
            sm += min(s[i], abs(g[i] - c * w[i])) if g[i] - c * w[i] <= 0 else 0
            sM += s[i] if s[i] - c * w[i] <= 0 else c * w[i]
            gm += min(g[i], abs(s[i] - c * w[i])) if s[i] - c * w[i] <= 0 else 0
        
        if gM >= a and sM >= b and gM + sm >= a + b:
            end = mid - 1
            answer = min(answer, mid)
        else:
            start = mid + 1
        
    return answer

print(solution(10, 10, [100], [100], [7], [10])) # 50