프로그래머스 - 금과 은 운반하기 java

문제 출처
금과 은 운반하기

해당 문제를 보자마자 어떤 식으로 풀어야될지 아예 감을 잡지 못했다. 그래서 이곳저곳을 참고했지만 문제를 완벽하게 이해하지 못했다.
어떻게 보자마자 이분탐색이라고 알게 될까.. 비슷한 문제를 열심히 풀어야되겠다.

참고사이트
https://prgms.tistory.com/101
https://stritegdc.tistory.com/260

특정시간을 이용하여 해당 시간안에 금과 은을 a,b 만큼을 옮길 수 있는지를 판단하며 운반시간을 조정해준다.

1. 최대시간은 최대 금과 은의 무게와 최대로 걸릴 수 있는 시간을 곱해서 설정
2. 최저시간과 최대시간을 이용하여 운반시간을 설정
3. 각 도시마다 금과 은을 최대로 옮길 수 있는지 판단한다.
   • 금을 먼저 우선순위로 생각하여 최대한 옮길 수 있는 양
   • 은을 먼저 우선순위로 생각하여 최대한 옮길 수 있는 양
   • 특정 시간안에 옮길 수 있는 금과 은의 최대 무게
4. 운반 가능한지 판단( 금과 은의 최대 무게가 주어진 a, b보다 큰 경우, 각각 금과 은이 a,b보다 큰 경우 운반가능, 아니면 불가능)

import java.util.*;

class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        long answer = -1;
        long left = 1;
        long right = (long)(10e9 * 2 * 10e5 * 2); // 최대 금,은의 무게 * 최대 시간
        
        while(left <= right)
        {
            int total =0;
            int gold = 0;
            int silver = 0;
            //운반 시간
            long mid = (left + right) / 2;
            
            for(int i = 0 ; i < g.length; i++)
            {
                int time = t[i];
                int weight = w[i];
                //몇번 왕복 운반해야되는지
                long cnt = mid / (time * 2);
                //편도로 운반해야되는 경우
                if(mid % (time * 2 ) >= time)
                {
                    cnt++;
                }
                //해당 시간에 옮길수 있는 무게
                long tmp = Math.min(g[i] + s[i] , weight * cnt);
                total += tmp;
                //금 최대 무게 누적
                gold += Math.min(g[i],tmp);
                //은 최대 무게 누적
                silver += Math.min(s[i],tmp);
                
            }
            
            if( total >= a + b && gold >= a && silver >= b)
            {
                right = mid - 1;
                answer = mid;
            }else{
                left = mid + 1;
            }
            
        }
        return answer;
    }
}