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

 

이분탐색 알고리즘.

 

이분탐색이라는 알고리즘을 알아도

 

Gmax = 골드 우선 탐색

 

Smax = 실버 우선 탐색 

 

이라고 했을 때 

 

a + b <= Gmax + Smin = Gmin + Smax = add 라는걸 알기 어려운 문제였다.

 

https://prgms.tistory.com/101

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

 

특정 시간 t에서

 

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

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

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

 

이세가지 값을 가지고 a + b <= Gmax + Smin = Gmin + Smax = add 이조건을 만족한다면 현재 t시간은 a, b를 운반할 수 있다를 결정할 수 있게된다.

 

 

function solution(a, b, g, s, w, t) {
    let answer = 10e5 * 4 * 10e9;
    
    let start = 0;
    let end = 10e5 * 4 * 10e9;
    
    while( start <= end) {
        let mid = Math.floor((start + end) / 2);
        let gold = 0;
        let silver = 0;
        let add = 0;
        
        for( let i =0; i < s.length; i++ ) {
            let now_g = g[i];
            let now_s = s[i];
            let now_w = w[i];
            let now_t = t[i];
            
            let move_cnt = Math.floor(mid / (now_t * 2));
            if(mid % (now_t * 2) >= t[i]) move_cnt++;

            gold += (now_g < move_cnt * now_w) ? now_g : move_cnt * now_w;
            silver += (now_s < move_cnt * now_w) ? now_s : move_cnt * now_w;
            add += (now_g + now_s < move_cnt * now_w) ? now_g + now_s : move_cnt * now_w;
        }
        
        
        if(gold >= a && silver >= b && add >= a + b) {
            end = mid - 1;
            answer = Math.min(mid, answer);
        }else {
            start = mid + 1;
        }
    }
    
    return answer;
}