금과 은 운반하기

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

이 문제를 해결할때 잘 접근 했던 것은 입출력 값의 크기를 보고 판단한 것이다. 문제를 읽고 스케쥴링 문제라고 생각을 했지만 입출력 값의 크기를 보고 스택으로 해결해서는 안된다는 것을 깨닫게 된 것 까지는 좋았다.

이 후 이 문제가 특정 시간이 제한된다는 것 최소 시간과 최대 시간을 계산할 수 있다는 것을 고려하였을때 Binary Search, 이진 탐색을 활용하여 문제를 해결해야 한다는 것을 캐치해낸 것도 좋았다.

하지만 문제가 되는 부분은 분기점을 계산하는 것을 어떻게 계산해야 할지를 구하지 못했다는 것이었다.

우선 알아낸 부분은 시간을 기준으로 탐색을 해야 하므로 그 시간에 문제의 조건인 금과 은을 모두 운반이 가능해내는 것을 확인해내는 로직을 작성해야 한다는 것은 알아냈다.

하지만 내부적인 로직과 최대 값의 범위를 어떻게 구해야 할지에 대해서 생각하지 못했다.

이진 탐색의 마지막 부분인 최대 값 계산하기

이진 탐색으로 문제를 해결할 경우 탐색하고자 하는 범위를 구하는 것이 가장 중요하다. 이 문제를 해결하지 못했던 이유 중 하나가 이 범위를 제대로 측정하지 못했다는 것이었다.

제한사항

- 0 ≤ `a`, `b` ≤ 10^9
- 1 ≤ `g`의 길이 = `s`의 길이 = `w`의 길이 = `t`의 길이 = 도시 개수 ≤ 10^5
    - 0 ≤ `g[i]`, `s[i]` ≤ 10^9
    - 1 ≤ `w[i]` ≤ 10^2
    - 1 ≤ `t[i]` ≤ 10^5
    - `a` ≤ `g`의 모든 수의 합
    - `b` ≤ `s`의 모든 수의 합

문제에서 주어진 조건은 한 트럭이 운반할 수 있는 무게의 제한이 존재하고 또한 한 도시에 있는 운반 가능한 금과 은의 무게 또한 제한이 있다는 것이다. 그리고 한 번 편도로 움직일 때마다 소요되는 시간이 존재한다는 것이 이 문제의 조건이었다.

그래서 이 문제의 최대 시간을 계산 했을때 나는 Math.pow(10, 9) / Math.pow(10, 2) * Math.pow(10, 5)를 최대 값으로 계산 했습니다.

이것을 풀어보면 다음과 같습니다.

• Math.pow(10, 9): 필요한 금 또는 은의 최대량 (109 kg)
• Math.pow(10, 2): 트럭 한 번 운반량의 최댓값 (100 kg = 102 kg)
• Math.pow(10, 5): 편도 이동 시간의 최댓값 (105 시간)

이 계산식은 109 kg의 광물을 트럭의 최대 운반량인 102 kg으로 나눈 후, 편도 시간의 최댓값인 105를 곱한 형태입니다.

최대 필요한 광물량 / 트럭 최대 운반량 × 최대 편도 시간

하지만 이는 잘못된 계산이었습니다. 여기서 재가 고려하지 못한 것은 트럭이 왕복으로 움직인다는 점을 고려하지 못한 것이었습니다.

따라서, 최악의 경우 (가장 많은 광물을, 가장 느린 트럭으로, 가장 작은 용량으로 운반할 때)의 max 시간은 다음과 같이 계산될 수 있습니다:

• 최악의 경우 필요한 최대 광물의 양은 10^9 + 10^9
• 가장 느린 트럭의 최솟값은 1
• 트럭의 최대 왕복 시간은 10^5 인데 왕복이므로 10^5 * 2

위의 값들을 모두 종합 하여 계산하면 (2×10^9)/1×(2×10^5)=4×10^14 가 되어 이 값이 최악의 경우 생길 수 있는 최대 시간의 범위가 됩니다.

조건 찾아내기

이 조건을 계산할때 재가 잘못 생각을 했던 것은 해당 시간이 주어진 조건을 통과하는지만 찾아내면 된다는 것이었습니다. 즉, 특정한 조건 정확한 계산을 하는 것이 아닌 말 그대로 조건을 통과하는지만 찾아내면 되는 것이 이진 탐색의 조건 함수로 사용할 때 알아야한다는 것을 잊어서는 안된다는 것을 배웠습니다.

function check(time) {
  let totalPossibleGold = 0;
  let totalPossibleSliver = 0;
  let totalPossibleWeight = 0;
  for (let i = 0; i < N; i++) {
    const roundTrip = t[i] * 2;
    let maxTrip = Math.floor(time / roundTrip);
    const remainTrip = time % roundTrip;
    if (remainTrip >= t[i]) {
      maxTrip += 1;
    }

    const maxGoldTrip = Math.min(w[i] * maxTrip, g[i]);
    const maxSliverTrip = Math.min(w[i] * maxTrip, s[i]);

    totalPossibleGold += maxGoldTrip;
    totalPossibleSliver += maxSliverTrip;
    totalPossibleWeight += Math.min(maxTrip * w[i], g[i] + s[i]);
  }

  return (
    totalPossibleGold >= a &&
    totalPossibleSliver >= b &&
    totalPossibleWeight >= a + b
  );
}

이 문제의 경우 위의 값을 보면 정확한 값을 계산하고 있지 않습니다.

const maxGoldTrip = Math.min(w[i] * maxTrip, g[i]);

이 코드의 경우 최대로 왕복할 수 있는 횟수에 운반 가능한 최대 은의 개수를 구한 후 해당 값을 그냥 전체 은의 값에 더하고 이 로직은 다른 방법에서도 동일하게 적용하고 있습니다.

그리고 이 후 조건으로

totalPossibleGold >= a &&
totalPossibleSliver >= b &&
totalPossibleWeight >= a + b

문제의 조건, a와 b 가 초과되게끔 정확하게 일치하지 않아도 초과할 수 있어 조건을 달성할 수 있는지만을 검사하고 있다는 것을 찾고 정확한 값이 필요한 것은 시간이므로 시간만을 이진 탐색으로 정확한 값을 찾아내면 된다는 것을 배울 수 있었습니다.