[프로그래머스] 금과 은 운반하기
https://programmers.co.kr/learn/courses/30/lessons/86053?language=python3
코딩테스트 연습 - 금과 은 운반하기
어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다. 각 도시에는
programmers.co.kr
월간 코드 챌린지 시즌3 문제로 프로그래머스 Level 3에 올라와 있다.
월간 코드 챌린지 시즌3 9월 해설
코딩이 재미있는 사람들을 위한 챌린지! 프로그래머스에서 2021년 9월 9일, 10월 7일 두 번에 걸쳐 월간 코드 챌린지 시즌3가 진행 중 입니다. 2021년 9월 9일 19시 30분부터 22시 30분까지 진행된 시즌2
prgms.tistory.com
위의 해설을 참고하여 이분탐색으로 풀었다.
제한사항으로 봤을 때 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