프로그래머스 [Lv. 3] 금과 은 운반하기 {언어 : Python} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

def solution(a, b, g, s, w, t):
    answer = 4 * 10 ** 14
    left = 0
    right = 4 * 10 ** 14
    lenT = len(t)
    abAll = a + b
    while left <= right:
        middle = (left + right) // 2
        weightGold = weightSilver = weightAB = 0
        for i in range(lenT):
            currentGold = g[i]
            currentSilver = s[i]
            currentWeight = w[i]
            currentT = t[i]
            count = middle // (currentT * 2)
            if middle % (currentT * 2) >= currentT:
                count += 1
            totalWeight = count * currentWeight
            weightGold += min(currentGold, totalWeight)
            weightSilver += min(currentSilver, totalWeight)
            weightAB += min(currentGold + currentSilver, totalWeight)
        if weightGold >= a and weightSilver >= b and weightAB >= abAll:
            right = middle - 1
            answer = min(middle, answer)
        else:
            left = middle + 1
        
    return answer

풀이 방법

 

1. 초기 설정: 필요한 금(a)과 은(b), 각 도시의 자원과 운반 능력을 기반으로 이진 탐색을 위한 범위를 설정한다.
2. 이진 탐색: left와 right를 설정하고, 중간값(middle)을 계산하여 이 시간을 기준으로 운반 가능성을 평가한다.
3. 운반 가능량 계산: 각 도시의 금과 은을 기준으로, middle 시간 내에 트럭이 몇 번 왕복할 수 있는지를 계산한다. 이를 통해 각 도시에서 운반할 수 있는 최대 금과 은의 양을 누적한다.
4. 조건 검사: 누적된 금과 은의 양이 필요량(a와 b)을 충족하는지 확인한다. 충족하면 right를 줄이고, 그렇지 않으면 left를 늘린다.
5. 결과 반환: 이진 탐색을 반복하여 찾은 최소 시간을 반환한다.

 

 

느낀점

• 전혀 방법이 떠오르지 않았고 이진탐색을 이렇게 사용한다고? 하는 느낌을 얻었다.