문제링크

문제설명

어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다.

각 도시에는 번호가 매겨져 있는데, i번 도시에는 금 g[i] kg, 은 s[i] kg, 그리고 트럭 한 대가 있습니다. i번 도시의 트럭은 오직 새 도시를 짓는 건설 장소와 i번 도시만을 왕복할 수 있으며, 편도로 이동하는 데 t[i] 시간이 걸리고, 최대 w[i] kg 광물을 운반할 수 있습니다. (광물은 금과 은입니다. 즉, 금과 은을 동시에 운반할 수 있습니다.) 모든 트럭은 같은 도로를 여러 번 왕복할 수 있으며 연료는 무한대라고 가정합니다.

정수 a, b와 정수 배열 g, s, w, t가 매개변수로 주어집니다. 주어진 정보를 바탕으로 각 도시의 트럭을 최적으로 운행했을 때, 새로운 도시를 건설하기 위해 금 a kg과 은 b kg을 전달할 수 있는 가장 빠른 시간을 구해 return 하도록 solution 함수를 완성해주세요.

풀이

Parametric Search에 대해 처음 배울 수 있는 문제였습니다.
최적화 문제를 결정 문제로 환원하는 방법입니다.
최소의 시간은 얼마인가? -> 이 시간대에 운반이 가능한가?
로 생각을 전환해서 풀면 접근이 훨씬 쉽습니다.

이분탐색을 사용합니다.
지정한 시간대에 검사할 조건은 3가지입니다.
1. 금을 우선적으로 옮겼을 때 금을 모두 옮길 수 있는가?
2. 은을 우선적으로 옮겼을 때 은을 모두 옮길 수 있는가?
3. 1번과 2번 중 하나를 선택했을 때, a + b kg 보다 같거나 큰 무게를 옮기고 있는가?
-> 전체 조건에 대해 조금 더 설명하면, 금과 은은 1대 1의 비율로 옮길 수 있습니다. 금과 은을 각 목표치보다 더 많이 옮길 수 있고, 그 합보다 더 많이 운반하고 있다면 목표치에 해당하는 금과 은도 운반이 가능합니다.

function solution(a, b, g, s, w, t) {
    const cityLen = g.length
    let start = 0
    let end = 10e14 * 4
        
    while( start <= end ){
        const mid = Math.floor((start + end) / 2)
        
        const [gMax, sMin] = findGmaxSet(mid)
        const [gMin, sMax] = findSmaxSet(mid)
        
        const passConstraint = (gMax >= a && sMax >= b && a + b <= gMax + sMin)
        
        if(passConstraint)
            end = mid - 1
        else
            start = mid + 1
    }
    
    return start
    
    
    function findGmaxSet( time ){
        let gMax = 0
        let sMin = 0
        for(let i = 0; i < cityLen; i++){
            const [tmpG, tmpS] = calcGmaxSet( i, time)
            gMax += tmpG
            sMin += tmpS
        }
        return [gMax, sMin]
    }
    
    function findSmaxSet( time ){
        let sMax = 0
        let gMin = 0
        for(let i = 0; i < cityLen; i++){
            const [tmpG, tmpS] = calcSmaxSet( i, time)
            gMin += tmpG
            sMax += tmpS
        }
        return [gMin, sMax]
    }
    
    function calcGmaxSet( idx, time ){
        const availableTrip = Math.round(time / (t[idx]*2))
        const totalAmount = availableTrip * w[idx]
        const gMax = calcMaxAmount( idx, totalAmount, g)
        const sMin = gMax < totalAmount ? calcMaxAmount( idx, totalAmount - gMax, s) : 0
        return [gMax, sMin]
    }
    
    function calcSmaxSet( idx, time ){
        const availableTrip = Math.round(time / (t[idx]*2))
        const totalAmount = availableTrip * w[idx]
        const sMax = calcMaxAmount( idx, totalAmount, s)
        const gMin = sMax < totalAmount ? calcMaxAmount( idx, totalAmount - sMax, g) : 0
        return [gMin, sMax]
    }
        
    function calcMaxAmount( idx, totalAmount, category ){
        const amount = category[idx]
        if( amount >= totalAmount) return totalAmount
        else return amount
    }
}