[ 프로그래머스 ] 금과 은 운반하기 JS LV3

https://school.programmers.co.kr/learn/courses/30/lessons/86053

프로그래머스

최근 알고리즘 문제 중에 가장 오래 걸린 문제였다..

풀이 방법

신도시의 필요한 자원을 모두 운반할 수 있는 가장 빠른 방법을 찾아야 한다. 단순 구현으로 풀 수는 있지만 시간 초과가 날 수 있어서 이진 탐색으로 방향을 바꿨다. 이진 탐색에서 중요한 건 어떤 기준을 잡고 검사할지와 최대 값을 정하는 부분이다.

---

최악의 경우 구하기

가장 빠른 시간을 구해야 하므로 기준은 시간을 잡는다. 최소 시간은 1이고, 최악의 시간은 아래와 같은 조건에서 발생한다.

• 트럭의 수 = 1
• 트럭의 짐칸 = 1
• 트럭의 편도 시간 = 10^5
• 필요 자원 = 금(10^9 ) + 은(10^9)

트럭이 한 번에 1씩밖에 운반할 수 없으므로, 2 * 10^9의 자원을 모두 옮기려면 총 2 * 10^9번의 왕복이 필요하다.

왕복 시간은 한 번의 편도 시간(10^5초) × 2다. 즉, 한 번 왕복하는 데 2 × 10^5초가 걸린다.

총자원을 모두 운반하려면 2 * 10^9번의 왕복이 필요하고, 한 번 왕복하는 데 2 * 10^5초가 걸리므로

(2 * 10^9) * (2 * 10^5) 즉 4 * 10^14가 된다.

 

위의 범위 내에서 이진탐색을 통해 가장 빠른 시간을 구한다.

---

시간 내 물자 조달 성공 여부 검사

이진 탐색을 하면서 주어진 시간 안에 물자 조달이 완료되는지를 확인해야 한다. 트럭이 왕복할 수 있는 횟수는 time / (트럭 왕복 시간)이다. 모든 트럭은 물자가 있는 도시에 위치하고 있다. 예를 들어:

• 시간: 10초
• 트럭의 편도 시간: 3초

이 경우 왕복 시간은 6초가 되며, 10 / 6 = 1번 왕복할 수 있다. 남은 시간이 4초인데, 편도 시간(3초) 보다 크거나 같으면 한 번 더 편도로 물자를 운반할 수 있다.

물자 조달 성공 여부는 3가지 조건이 만족해야 성공했다고 볼 수 있다.

1. 시간 내에 총 옮길 수 있는 금의 양 >= 필요로 하는 금
2. 시간 내에 총 옮길 수 있는 은의 양 >= 필요로 하는 은
3. 시간 내에 총 옮길 수 있는 전체 자원의 양 >= 필요로 하는 금 + 은

3번을 체크하는 이유는 시간 내에 금과 은을 동시에 옮기기 때문이다. 만약 트럭의 한도가 50이라면 금 50과 은 50을 함께 옮기고 있다. 이건 불가능하다. 예시로

• 필요 자원 = 금 50 은 50
• 트럭 짐칸 = 50
• 도시 자원 = 금 100 은 100
• 조달 가능한 횟수 = 1

시간 내에 금 50개 또는 은 50개를 옮길 수 있다. 1번 과 2번 조건만 본다면 성공적으로 물자 조달이 가능하지만 실제로는 트럭 짐칸을 초과하기 때문에 3번의 조건으로 체크할 수 있다.

• 위와 동일
• 조달 가능한 횟수 = 2

위와 같은 경우라면 1, 2, 3번 조건 모두 성립해 성공적으로 물자 조달을 했다고 볼 수 있다.

---

코드

function check(time,a,b,g,s,w,t){
    let sumA = 0;
    let sumB = 0;
    let total = 0;
    
    for (let i = 0; i < t.length; i++){
        let cnt = Math.floor(time / (t[i] * 2));
        if (time % (t[i] * 2) >= t[i]) cnt++;
        let W = w[i] * cnt;
        sumA += Math.min(W, g[i]);
        sumB += Math.min(W, s[i]);
        total += Math.min(W, g[i] + s[i]);
        if (sumA >= a && sumB >= b && total >= a + b) return true
    }
    return false;
}

function solution(a, b, g, s, w, t) {
    var answer = Infinity;
    let start = 1;
    let end = 4 * Math.pow(10,14);

    while(start <= end){
        let mid = Math.floor((end + start) / 2);
        
        if (check(mid,a,b,g,s,w,t)){
            end = mid - 1;
            answer = Math.min(answer , mid)
        }
        else {
            start = mid + 1;
        }
    }
    return answer
}