[pro] 프로그래머스 level3 86053 금과 은 운반하기 (Java) - 이분탐색

[문제]

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

프로그래머스

 

[풀이]

먼저 이분탐색을 생각해내야 한다...(어떻게 생각해내는건지?)

금 a와 은 b를 전달하기 위한 가장 빠른 시간을 구하자!가 아닌, 특정 시간 t 안에 금 a와 은 b를 운반할 수 있는지를 확인하고, 운반 가능하면 시간을 줄이고, 불가능하면 시간을 늘리도록 한다.

 

이분탐색을 하려면 min, max (left, right) 값을 설정해줘야 하는데, min 값은 1초로 해주었다. max 값은 (10^9 * 2 * l0^5 * 2) 로 해주었는데 이는 (운반해야 하는 최대 금의 양 10^9 + 최대 은의 양 10^9) / 1(한번에 옮길 수 있는 무게) * (옮기는데 걸리는 시간) * 2(왕복 운반) 에 따라 결정되었다.

 

그 다음에는 모든 도시를 순회하면서 금과 은을 운반한다. 

운반 시간 mid가 11초이고, t[i]가 2초라고 가정하자. 왕복 이동에 4초가 소요되기 때문에 총 11/4=2번 왕복이 가능하다. 또한 11%4=3 >= 2 이므로 한번 더 편도 이동이 가능하다. 즉 총 3번 금과 은을 운반할 수 있다.

위처럼 운반 횟수를 구할 수 있고, 이를 통해 금과 은을 얼마나 운반할 수 있는지 알 수 있다. 이 때 확인해줘야 하는 것은 다음 3가지이다.

1) 금을 얼마나 운반할 수 있는가?

2) 은을 얼마나 운반할 수 있는가?

3) 금+은을 얼마나 운반할 수 있는가?

최대 w[i] 만큼 운반이 가능하고, 이는 금과 은을 모두 합한 무게이다. 따라서 금과 은 뿐 아니라, 금과 은을 합친 광물의 양을 옮길 수 있는지도 판단해줘야 한다. 

 

 

[코드]

 

class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        long answer = -1;
        //금 a kg과 은 b kg을 전달할 수 있는 가장 빠른 시간을 구해 return
    
        long left = 1;
        long right = (long)(10e9 * 2 * 10e5 * 2);
        int len = s.length;
        
        while(left<=right){
            long mid = (left+right)/2; //운반 시간 지정
            
            //도시 순회
            int gold = 0, silver = 0, sum = 0;
            for(int i=0; i<len; i++){
                int weight = w[i];
                int time = t[i];
                
                //몇 번 왕복 운반 가능한지
                long cnt = mid/(time*2);
                if((mid%(time*2)) >= time){ //편도 추가 운반 가능한지
                    cnt++;
                }
                
                gold += Math.min(g[i], weight*cnt);
                silver += Math.min(s[i], weight*cnt);
                sum += Math.min(g[i]+s[i], weight*cnt);
            }
            
            //운반 가능하면 시간 줄이기
            if(gold>=a && silver>=b && sum>=a+b){
                answer = mid;
                right = mid-1;
            }
            else{
                left = mid+1;
            }
        }
        
        return answer;
    }
}