[Algorithm] 금과 은 운반하기

📋 문제

어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 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 함수를 완성해주세요.

제한사항

• 0 ≤ a, b ≤ 109
• 1 ≤ g의 길이 = s의 길이 = w의 길이 = t의 길이 = 도시 개수 ≤ 105
  
  • 0 ≤ g[i], s[i] ≤ 109
  • 1 ≤ w[i] ≤ 102
  • 1 ≤ t[i] ≤ 105
  • a ≤ g의 모든 수의 합
  • b ≤ s의 모든 수의 합

 

입출력 예

10	10	[100]	[100]	[7]	[10]	50
90	500	[70,70,0]	[0,0,500]	[100,100,2]	[4,8,1]	499

 

✏️ 풀이

이전에 풀었던 선입 선출 스케줄링과 비슷한 느낌을 받았기에 이분탐색으로 접근했다.  mid는 걸리는 시간을 의미한다.

 

left, right를 선언했다. right는 최대 시간이 되어야 하기 때문에 10^5(시간) * 10^9(무게) * 왕복(2)을 고려해서 넉넉하게 10^15로 선언해줬다. 옮길 수 있는 금과 은의 양을 확인하며 진행했다. for문을 사용하여 먼저 편도로 광석을 보낼 수 있는지를 확인했다. 왕복이라면 시간에 2를 곱한만큼 시간이 들기 때문에 현재 걸리는 시간인 mid를 시간 * 2로 나눈 나머지가 현재 시간보다 큰지를 확인했다. 그 다음 현재 도시에서 이동가능한 광석의 양(availableWeight)을 구했다. 왕복으로 보낼 수 있는 횟수(Math.floor(mid / (t[i] * 2)))에 한번에 보낼 수 있는 양(w[i])을 곱해주고 앞서 확인했던 마지막에 편도로 보낼 수 있는지를 확인해 여부에 따라 추가했다.

 

다음으로 현재 도시의 금, 은의 양과 비교하여 보낼 수 있는 금, 은의 양을 확인했다. 만약 보낼 수 있는 광석의 양보다 도시에서 보유한 금 또는 은이 작은 경우 보유한 금, 은 양을 더해주고 아닌 경우 앞서 구한 보낼 수 있는 양을 더했다. 

 

금과 은의 양이 모두 요구되는 양(a, b)보다 큰 경우 right를 mid로 바꿔주고 answer를 체크하여 최신화했다. 반대인 경우 left를 mid로 증가시킨다.

 

여기서 내가 고려하지 못했던 점이 있었는데 하나의 도시에서 금과 은을 모두 보유한 경우였다. 지금까지의 내 풀이에 따르면 문제의 첫 번째 예시를 기준으로 금과 은이 100씩 있을 때 위 설명대로 코드를 돌면 30이라는 결과가 나온다. 왜냐하면 보낼 수 있는 양이 금과 은에 모두 중첩되기 때문이다. 하나뿐인 도시에서 보낼 수 있는 양은 14지만 금과 은의 양을 각각 계산할 때 14라는 값을 두고 계산하기 때문이다. 이 문제를 해결하기 위해 고민을 많이 했으나 결국 다른 분의 풀이를 참고했다.

 

해결방법은 total이라는 변수를 하나 더 두는 것이었다. 보낼 수 있는 금과 은의 양을 계산할 때와 마찬가지로 보유한 금 + 보유한 은과 구한 보낼 수 있는 양을 비교하여 더해가준다. 문제의 첫 번째 예시를 기준이로 14라는 보낼 수 있는 값이 나왔을 때 금과 은의 총량은 20이므로 total에는 14가 할당되고 필요한 금, 은을 비교하는 아래 조건문에서 total값도 확인해준다.(total >= a + b) 두 광물 모두 보낼 수 있다면 유동적으로 필요한 광석을 보내면 되는데 이때 보낼 수 있는 양이 필요한 양을 초과하는지 확인하면 되는 거였다...!

 

⌨️ 코드

function solution(a, b, g, s, w, t) {
  var answer = Infinity;

  const n = g.length;

  let left = 1;
  let right = 10 ** 15;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    let gold = 0;
    let silver = 0;
    let total = 0;
    for (let i = 0; i < n; i++) {
      const canOneWay = mid % (t[i] * 2) >= t[i];
      let availableWeight = Math.floor(mid / (t[i] * 2)) * w[i];
      if (canOneWay) availableWeight += w[i];

      gold += availableWeight > g[i] ? g[i] : availableWeight;
      silver += availableWeight > s[i] ? s[i] : availableWeight;
      total += availableWeight > s[i] + g[i] ? s[i] + g[i] : availableWeight;
    }

    if (gold >= a && silver >= b && total >= a + b) {
      right = mid;
      answer = Math.min(answer, mid);
    } else {
      left = mid + 1;
    }
  }

  return answer;
}