금과 은 운반하기

1. 금과 은 운반하기

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

---

2. 나만의 문제 해결

수학적인 접근이 필요한 문제라고 생각했다.
개인적으로 정말 어려웠던 문제였고, 다른 블로그 풀이를 보고 이해를 했다.

참고

<핵심 풀이과정>
1. 금을 우선으로 운반한 경우 금과 은의 양 -> Gmax, Smin 정의,
2. 은을 우선으로 운반한 경우 금과 은의 양 -> Gmin, Smax 정의한다면,

a <= Gmax
b <= Smax
a + b <= Gmax + Smin = Gmin + Smin을 만족,

주어진 시간 T 안에 a만큼의 금과 b만큼의 은을 운반할 수 있다.

T < t 일 경우는 전부 운반 불가능, t <= T 일 경우는 전부 운반 가능하므로,
이 t 값을 이분탐색으로 찾으면 답을 도출할 수 있다!

t의 최댓값은 최악의 경우 걸리는 시간이므로,
[(금의 양)+(은의 양) / (한번에 옮길 수 있는 무게)] X (옮기는데 걸리는 시간 X 2)
최악의 경우 = ((10^9+10^9) / 1) 10^5 2

---

3. code

class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        //((금의 양)+(은의 양) / (한번에 옮길 수 있는 무게)) * (옮기는데 걸리는 시간 * 2)
        // 최악의 경우 = ((10e9+10e9) / 1) * 10e5 * 2
        long end = (long) (10e9 * 2 * 10e5 * 2);
        long start = 0;
        long answer = end;

        //이분탐색 시작
        while (start <= end) {
            long mid = (start + end) / 2;
            int gold = 0;
            int silver = 0;
            int add = 0;

            //각각의 도시에서 시간안에 움직일 수 있는 금,은 양의 합
            for (int i = 0; i < g.length; i++) {
                int cityGold = g[i];
                int citySilver = s[i];
                int weightCanMove = w[i];
                long oneWayTime = t[i];

                long moveCount = mid / (oneWayTime * 2);
                //나머지가 t[i]보다 크거나 같다면 한번 더 움직여야 함
                if (mid % (oneWayTime * 2) >= t[i]) {
                    moveCount++;
                }

                //+= 현재 도시에서 금을 이동시킬 수 있는 촤대의 양
                gold += Math.min(cityGold, moveCount * weightCanMove);
                //+= 현재 도시에서 은을 이동시킬 수 있는 촤대의 양
                silver += Math.min(citySilver, moveCount * weightCanMove);
                //+= 현재 도시에서 금과 은을 이동시킬 수 있는 촤대의 양
                add += Math.min(cityGold + citySilver, moveCount * weightCanMove);
            }
            
            //운반이 가능하다면
            if (a <= gold && b <= silver && a + b <= add) {
                end = mid - 1;
                answer = Math.min(mid, answer);
                continue;
            }
            
            //운반이 불가능 하다면
            start = mid + 1;
        }

        return answer;
    }
}