[Lv.3] 금과 은 운반하기 - 자바

class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {

        long left=0;
        long right=(long)(10e9*2*10e5*2);
        long answer = right;

        while (left<=right){
            long mid=(left+right)/2;
            long gold,silver,sum;
            gold=silver=sum=0;
            for (int i = 0; i < g.length; i++) {
                long move=mid/(2*t[i]);
                if(mid%(t[i]*2)>=t[i]){
                    //현재 시간(mid)에서 왕복하고 남은 시간이 편도 보다 크거나 같다면 한번 더 가도 됨
                    move++;
                }
                //현재 시간만큼 왕복해서 자원을 채취한다
                //현재 시간에 자원을 모두 캘 수 있다면 모두 캐고, 그렇지 않다면 캘 수 있는 만큼만 캔다
                gold+=Math.min(g[i],move*w[i]);
                silver+=Math.min(s[i],move*w[i]);
                sum+=Math.min(g[i]+s[i],move*w[i]);
            }
            if(a<=gold&&b<=silver&& a+b<=sum){
                right=mid-1;
                answer=Math.min(mid,answer);
            }else left=mid+1;
        }

        return answer;
    }
}

오랜만에 풀어보니 어떻게 풀 지 감도 오지 않아 풀이를 참고하여 풀었다..

시간을 대상으로 뭔가 해야될 거 같긴 헀는데, 순차적으로 시간을 돌고 거기에 모든 도시를 매번 탐색하게 되면 최대 10^10의 반복이 생기기에 절대 정답이 아니라고 생각하여 고민을 하다 결국 포기하고 풀이를 보았다.

 

키워드는 이분탐색과 금과 은의 채굴량인 것 같다.

우선 기존에 고민했었던, 시간을 탐색하는것은 시간 자체를 이분탐색을 하게 되면 해결된다.

여기서 최대값은 왕복해서 채굴하는데에 걸리는 시간 * 최대 채굴량이다.

즉, 2*10^5*(10^9+10^9)이다.

주어진 시간동안 채굴량의 경우, 시간을 해당 도시의 왕복 소요 시간으로 나누어 가능한 왕복 횟수를 먼저 구하고( 만약 편도로 한 번 더 갈 수 있으면 간다)

금을 최대한 캐고, 은을 최대한 캔다. ( 모든 자원을 캐거나, 주어진 방문 횟수만큼 자원을 캔다)

또, 이 둘의 합을 저장한다( 마찬가지로, 금,은을 모두 캐거나, 주어진 방문 횟수만큼 자원을 캔다)

 

이렇게 해당 시간에 모든 도시에서 자원을 캔 결과를 들고, 이 값이 채취해야하는 자원을 모두 넘겨서 채취하였으며, 채취한 자원의 합이 캐야하는 금과 은의 양보다 크다면 해당 시간에선 자원을 모두 배달하는게 가능하므로 right를 땡겨준다.

아니면, left를 땡겨온다.

 

코드 자체는 짧고 간결한데, 이분 탐색으로 풀 생각 그리고, 자원 채취 방식을 쉽게 떠올리기 힘들었다.

ㅠㅠ