[Programmers] 금과 은 운반하기 (Java)

1.  문제 링크

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

2.  문제

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

3.  제한사항

• 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의 모든 수의 합

입출력 예

4.  소스코드

class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        long answer = binarySearch(a, b, g, s, w, t);
        return answer;
    }

    public long binarySearch(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        int cityNum = g.length;
        // ((금의 양) + (은의 양) / (한 번에 옮길 수 있는 무게)) * (윪기는데 걸리는 시간 * 2)
        // 조건에서 금, 은의 양의 최대 = 10e9, 올길 수 있는 무게 최소값 = 1, 옮기는데 걸리는 시간의 최대 = 10e5
        long start = 0, end = (long)(10e9 * 2 * 10e5 * 2);
        long answer = end;
        while(start <= end) {
            long mid = (start + end) / 2;
            int gold = 0, silver = 0, sum = 0;
            for(int idx = 0; idx < cityNum; idx++) {
                long move = mid / (t[idx] * 2);
                if(mid % (t[idx] * 2) >= t[idx]) move++;

                gold += Math.min(g[idx], move * w[idx]);
                silver += Math.min(s[idx], move * w[idx]);
                sum += Math.min(g[idx] + s[idx], move * w[idx]);
            }

            if(a <= gold && b <= silver && a + b <= sum) {
                end = mid - 1;
                answer = Math.min(answer, mid);
                continue;
            }
            start = mid + 1;
        }
        return answer;
    }
}

5.  접근

• 이 문제를 t라는 시간이 주어졌을 때, t 시간 안에 금과 은을 각각 a, b만큼 운반할 수 있는지 판별하는 문제로 바꿔서 해결합니다.
• 금을 우선으로 운반한 경우에 금과 은의 양을 각각 Gmax, Smin이라고 표현하고 은을 우선으로 운반한 경우에 금과 은의 양을 Gmin, Smax라고 표현하겠습니다.
• 결국 t 시간 안에 금과 은을 각각 a, b만큼 운반하기 때문에 Gmax + Smin = Gmin + Smax가 됩니다.
• 만약 a가 Gmax보다 작거나 같고 b가 Smax보다 작거나 같으며 a + b가 Gmax + Smin = Gmin + Smax보다 작거나 같다면 주어진 시간 t 안에 금과 은을 각각 a, b만큼 운반할 수 있습니다.
• 이를 이용하여 시간에 대한 이분탐색을 통해 금 a와 은 b를 전달할 수 있는 가장 빠른 시간을 구합니다.