[프로그래머스] (86053) 금과 은 운반하기

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

사용 언어 : JAVA

---

 

---

풀이

변수, 조건 정리

• a : 신도시에 필요한 금 총량
• b : 신도시에 필요한 은 총량
• g[i] : i번째 도시가 가지고 있는 금 총량
• s[i] : i번째 도시가 가지고 있는 은 총량
• w[i] : i번째 도시가 트럭에 적재할 수 있는 최대 적재량
• t[i] : i번째 도시에서 신도시까지 편도로 이동 시 걸리는 시간

각 도시에서 출발하는 모든 트럭은 동시에 운행할 수 있으며, 마지막까지 움직이는 트럭의 이동 시간까지만 구하면 된다.

 

아이디어

목표
금 a kg과 은 b kg을 전달할 수 있는 가장 빠른 시간을 구한다.

이럴 때 사용할 수 있는게 이분 탐색이다. 스무고개 하 듯이 'X시간에는 (a, b) kg를 운반할 수 있는가?', '(가능하다면) X/2시간에는 가능한가?', '(불가능하다면) X*(3/2)시간에는 가능한가?' 를 물어보며 불가능과 가능의 경계점을 찾는 것이다.

 

시간 T 내에 (a, b) kg 만큼 옮기는 것이 가능하다/불가능하다 를 결정짓는 기준은 세가지가 있다.

1. 시간 T 내에 모든 도시에서 금을 옮길 수 있을 만큼 옮겼을 때 a kg를 채울 수 있는가.
2. 시간 T 내에 모든 도시에서 은을 옮길 수 있을 만큼 옮겼을 때 b kg를 채울 수 있는가.
3. 시간 T 내에 옮길 수 있는 최대 무게를 옮겼을 때 (a+b) kg를 채울 수 있는가.

이 세가지 조건을 모두 만족하였을 때 시간 T 내에 (a, b) kg 만큼 옮기는 것이 가능하다고 말할 수 있으며, 이것이 이분 탐색의 조건이 된다.

 

최종 코드

import java.util.*;

class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
    
        long min = 0L;
        // 최대값 : 최대 적재량이 1이고 편도 이동 시간이 100,000일때
        // => ((a+b)의 최댓값)번 * 왕복 최대 시간 (정확히는 (편도*2-1)이지만 편의상 왕복으로 측정)
        // == 2,000,000,000 * 200,000
        long max = 400000000000000L;
        long mid;
        
        // 이분 탐색
        // min일 때 불가능하고 (min+1 == max)일 때 가능하다면 max가 최소 시간이 됨
        while(min+1 < max) {
            mid = (min+max) / 2;
            
            // mid 시간에 (a, b)kg를 옮길 수 있는가?
            if(IsPossibleInTime(mid, a, b, g, s, w, t)) {
                max = mid;
            } else {
                min = mid;
            }
        }
        
        return max;
    }
    
    public boolean IsPossibleInTime(long time, int a, int b, int[] g, int[] s, int[] w, int[] t) {
        int n = g.length;
        
        // time 시간동안 모든 도시에서 옮길 수 있는 최대 금, 은, 적재 가능 무게.
        long totalG = 0L;
        long totalS = 0L;
        long total = 0L;
        
        // i번째 도시에서 time 시간동안 옮길 수 있는 최대 금, 은, 적재 가능 무게.
        long maxG, maxS, maxT;
        
        // time 시간 동안 편도로 움직일 수 있는 횟수
        long cnt;
        
        for(int i=0; i<n; i++) {
            cnt = time / (t[i]*2L);
            if(time % (t[i]*2L) >= t[i]) cnt++;
            
            // cnt번 움직여서 옮길 수 있는 최대량 VS (가진 금 총량 / 가진 은 총량 / 가진 금+은 총량)
            maxG = Math.min(w[i] * cnt, g[i]);
            maxS = Math.min(w[i] * cnt, s[i]);
            maxT = Math.min(w[i] * cnt, g[i]+s[i]);
            
            totalG += maxG;
            totalS += maxS;
            total += maxT;
        }
        
        // cnt번 금/은 하나만 옮겼는데도 필요량을 충족하지 못한다 -> 시간 내에 불가능
        if(totalG < a || totalS < b) return false;
        
        // cnt번 옮길 수 있는 최대를 옮겼는데도 전체 필요량을 충족하지 못한다 -> 시간 내에 불가능
        if(total < a+b) return false;
        
        return true;
    }
}

---

느낀점

• JOHN, I'M TIRED