[JS] 금과 은 운반하기

 

 

 

상당히 어려운 문제였다.

 

프로그래머스 3단계쯤 들어와서부터는 절반쯤은 스스로 해결을 하지 못하는 것 같다.. (ㅜ)

 

이번 문제도 카카오에서 제공한 해설을 읽고 해결하였다!

 

문제에서 제공하는 무지막지한 테스트케이스에서 알 수 있듯이 일반적인 방식으로 문제를 접근하면 풀 수 없다. (완전탐색,DP등)

 

문제의 핵심은 이분탐색에 있었다.

 

 

 

gold = 특정 시간 t 동안 얻을 수 있는 최대 골드 수

silver = 특정 시간 t 동안 얻을 수 있는 최대 실버 수

add = 특정 시간 t 동안 골드와 실버를 한번에 얻을 수 있는 최대 수

 

 

라고 두었을때

 a + b <= Gmax + Smin = Gmin + Smax = add 

 

위 조건을 만족하는 최소의 t를 찾는 문제라고 접근하는 사고가 필요하다.

 

 

즉 금이랑 은을 조합해서 시간을 만드는 것이 아닌

 

시간을 쭉 나열하고 (시간은 오름차순 정렬이 되어있기 때문!) 해당 시간으로 금,은을 수거할 수 있는지를 파악하면 되는 문제였다.

 

 

발상이 되게 독특하고 재밌는 문제였다..

 

function solution(a, b, g, s, w, t) {
    let ret = 10e5 * 4 * 10e9;
    
    let start = 0;
    let end = 10e5 * 4 * 10e9;
    
    while(start <= end) {
        //초기값
        let [mid,gold,silver,add] = [Math.floor((start + end) / 2),0,0,0]
        
        for( let i =0; i < s.length; i++ ) {
            let curGold = g[i];
            let curSilver = s[i];
            let curWeight = w[i];
            let curTime = t[i];
            
            let cnt = Math.floor(mid / (curTime * 2));
            if(mid % (curTime * 2) >= t[i]) cnt++;

            gold += (curGold < cnt * curWeight) ? curGold : cnt * curWeight;
            silver += (curSilver < cnt * curWeight) ? curSilver : cnt * curWeight;
            add += (curGold + curSilver < cnt * curWeight) ? curGold + curSilver : cnt * curWeight;
        }
        
        
        if(gold >= a && silver >= b && add >= a + b) {
            end = mid - 1;
            ret = Math.min(mid, ret);
        }else {
            start = mid + 1;
        }
    }
    
    return ret;
}