[코딩테스트]#10. 금과 은 운반하기

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

 

제한사항

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

입출력 예

 

입출력 예 설명
입출력 예 #1

• 도시가 오직 하나뿐이므로, 0번 도시의 유일한 트럭이 모든 운반을 해결해야 합니다. 이 트럭은 최대 7kg만큼의 광물을 운반할 수 있으며 편도 완주에는 10시간이 걸립니다.
• 맨 처음에 10시간을 써서 7kg만큼의 금을 운반하고, 10시간을 써서 다시 도시로 돌아오고, 10시간을 써서 7kg만큼의 은을 운반하고, 10시간을 써서 다시 도시로 돌아오고, 마지막으로 10시간을 써서 3kg만큼의 금과 3kg만큼의 은을 운반하면, 총 50시간 만에 필요한 모든 금과 은을 조달할 수 있습니다.
• 따라서, 50을 return 해야 합니다.

입출력 예 #2

• 도시가 3개이고, 0번과 1번 도시는 금만 70kg씩 가지고 있고 2번 도시는 은을 500kg 가지고 있습니다.
  0번 도시의 트럭은 용량은 100kg, 편도 완주 시간은 4시간입니다.
  1번 도시의 트럭은 용량은 100kg, 편도 완주 시간은 8시간입니다.
  2번 도시의 트럭은 용량은 2kg, 편도 완주 시간은 1시간입니다.
• 금은 0번 도시의 트럭과 1번 도시의 트럭이 각각 45kg씩 나누어서 운반하면 8시간 안에 필요한 모든 금을 조달할 수 있습니다.
• 은은 2번 도시의 트럭이 한 번에 2kg씩 250번 운반하면(249번 왕복 + 1번 편도) 총 499시간 만에 필요한 모든 은을 조달할 수 있습니다.
• 따라서, 499를 return 해야 합니다.

풀이 요약

이분 탐색(BinarySearch)알고리즘 문제로 각 도시별로 금, 은 보유량과 운반 트럭의 정보를 받아 계산하여 해결하였다.

low = 가장 작은 값, high = 가장 큰 값으로 high는 금과은의 최대량(10e9+10e9)*최대 시간(10e5*2(왕복))/ 최대 운반 무게(100)을 적용하였다.

isPossible 함수를 통해 운반 성공 유무를 확인하여 low와 high값을 구했고 가장 적은 시간이 걸리는 low 값을 반환했다.

 

풀이 소스코드

 

class Solution {

    public  long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        long low = 0L;
        long high = 400000000000000L;

        while (low <= high) {
            long mid = (low + high) / 2L;

            if (isPossible(mid, a, b, g, s, w, t)) {
                high = mid - 1;
            } else {
                low = mid+1;
            }
        }

        System.out.println("low = " + low);
        return low;
    }

    private  boolean isPossible(long time, int a, int b, int[] g, int[] s, int[] w, int[] t) {
        int cityCnt = g.length;
        long sum = 0L;
        long sumG = 0L;
        long sumS = 0L;

        for (int i = 0; i < cityCnt; i++) {
            long cnt = time / (2L * t[i]);
            if (time % (2L * t[i]) >= t[i]) cnt+=1;

            long tmp = Math.min(cnt * w[i], g[i] + s[i]);
            sum += tmp;
            sumG += Math.min(tmp, g[i]);
            tsumS += Math.min(tmp, s[i]);
        }
        // 운반 만족 조건
        if (sum >= a + b && sumG >= a && sumS >= b) {
            return true;
        }
        return false;
    }
}