[프로그래머스] 월간 코드 챌린지 시즌3 | 금과 은 운반하기

 

 

---

금과 은 운반하기

---

 

문제 설명

어느 왕국에 하나 이상의 도시들이 있습니다. 

왕국의 왕은 새 도시를 짓기로 결정하였습니다. 

해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 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 해야 합니다.

 

 

 

 

---

    코드

---

 

class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        long answer = -1;
        return answer;
    }
}

 

---

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

        // 정답을 저장할 변수, 최대값으로 초기화
        // 일정 값 제거 : 너무 큰 값을 사용할 경우 오버플로우 방지
        long answer = Long.MAX_VALUE - 99999999;  
       // 이진 탐색의 최대 범위 (탐색해야 할 시간 범위의 최대값)
        long end = Long.MAX_VALUE - 99999999;  
       // 이진 탐색의 최소 범위 (탐색해야 할 시간 범위의 최소값)
        long start = 0; 
        // 도시의 개수
        long len = t.length; 


        // 이진 탐색 실행
        while(start <= end){  // 탐색 범위 설정
            long mid = ((end - start)/2) + start; // 중간 시간 값 계산

            long max_gold = 0; // 최대 금 운반량
            long min_gold = 0; // 최대 은의 경우 최소 금 운반량
            long max_silver = 0; // 최대 은 운반량
            long min_silver = 0; // 최대 금의 경우 최소 은 운반량

            // 모든 도시 계산
            for(int i=0; i<len; i++){ 
                long have_gold = g[i]; // i번 도시의 금
                long have_silver = s[i]; // i번 도시의 은
                long weight = w[i]; // i번 도시의 트럭 운반 능력
                long time = t[i]; // i번 도시의 트럭 이동 시간
                long count = (mid + time) / (2 * time); // 가능한 왕복 횟수

                long can_gold = 0; // 트럭이 운반하는 금의 양
                long can_silver = 0; // 트럭이 운반하는 은의 양
                long can_weight = 0; // 한번의 왕복에서 최대 광물의 총 무게
                long max_count = (a + b) / weight + 1; // 최대 왕복 횟수, + 1: 소수점 이하를 버릴 때 필요한 추가 왕복
                
                // 트럭이 실제로 운반할 수 있는 광물의 무게
                if(count > max_count){
                    can_weight = max_count * weight; // max_count에 의해 실제 운반할 수 있는 무게가 제한
                }else{
                    can_weight = count * weight;  // 실제 운반할 수 있는 무게 실제 왕복 횟수에 의해 결정
                }

                // 금을 우선적으로 운반할 때, 은을 얼마나 추가로 운반할 수 있는지
                if( can_weight > have_gold ){
                    can_gold = have_gold;
                    can_silver = Math.min((can_weight - can_gold), have_silver);
                }else{
                    can_gold = can_weight;
                }
                max_gold += can_gold;
                min_silver += can_silver;


                // 은을 우선적으로 운반할 때, 금을 얼마나 추가로 운반할 수 있는지
                can_gold = 0;
                can_silver = 0;
            
                if( can_weight > have_silver ){
                    can_silver = have_silver;
                    can_gold = Math.min((can_weight - can_silver), have_gold);
                }else{
                    can_silver = can_weight;
                }
                min_gold += can_gold;
                max_silver += can_silver;
            }

            // 운반 가능 여부
            // 중간 시간(mid)에서 필요한 금과 은을 모두 운반할 수 있음
            if( a <= max_gold && b <= max_silver && a + b <= max_gold + min_silver && a + b <= min_gold + max_silver ){
                end = mid - 1; // 중간값을 포함한 현재의 탐색 범위 상한 부분을 제외 탐색 범위 축소
                answer = mid;
            // 필요한 금과 은을 모두 운반할 수 없음
            }else{ 
                start = mid + 1; //  더 긴 시간 범위에서 다시 탐색
            }         
        }

        return answer;
    }
}

 

 

Long.MAX_VALUE : long 타입이 가질 수 있는 최대값

 

Long.MAX_VALUE - 99999999

- 이진 탐색 과정에서 오버플로우를 방지(long 타입 이상), 합리적인 최대 탐색 범위를 설정

- 10의 9승 = 1억

 

Long.MAX_VALUE - 99999999를 초기값과 결과 값 모두 사용하는 이유

- answer는 이론적으로 end 범위를 초과하는 값을 가질 수 있음

 

long start = 0;에서 start 변수를 0으로 설정하는 이유

- 가장 빠른(낮은) 시간에서 탐색을 시작하여 필요한 광물량을 충족할 수 있는지 확인

- 이진 탐색은 중간값을 반복적으로 조정하면서 올바른 해답을 찾아가는 방식, 최소값을 0으로 시작하는 것이 일반적 이진 탐색의 작동 원리

- 범위의 중간값(mid)을 계산하여 주어진 조건(여기서는 필요한 광물량을 수집하는 데 필요한 시간)을 만족하는지 확인

- 만족하지 않으면, mid 값을 기준으로 탐색 범위를 절반으로 감소

 

count (가능한 왕복 횟수 계산)

주어진 시간(mid) 동안 트럭이 최대 몇 번 왕복할 수 있는지

이진 탐색을 통해 결정된 시간(mid) 안에 트럭이 새 도시 건설 장소와 i번 도시를 몇 번 오갈 수 있는지

트럭이 실제로 운반 작업을 수행할 수 있는 시간적 한계

 

max_count (이론적 최대 왕복 횟수 계산)

이론적으로 필요한 모든 금(a kg)과 은(b kg)을 운반하기 위해 필요한 최대 왕복 횟수

트럭의 운반 능력(weight)에 따라 필요한 총 광물 무게를 운반하기 위해 필요한 왕복 횟수 광물의 무게적 한계

트럭이 한 번에 운반할 수 있는 최대 무게

 

can_gold와 can_silver 변수 0으로 초기화

- 변수를 재사용 하기 위해

- 정확한 계산을 위한 초기화

- 누적 계산 방지

 

---

 

고수님의 풀이와 차이점

class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        long answer = 400000000000000L;
        long low = 0;
        long high = 400000000000000L;
        long gold;
        long silver;
        long sum;
        long mid;
        while(low<=high){
            mid = (low+high) / 2;
            gold = 0;
            silver = 0;
            sum = 0;
            for(int i = 0; i < w.length; i++) {
                long moveCount = mid / (t[i]*2L);
                if (mid % (t[i]*2L) >= t[i]) moveCount++;
                gold += Math.min(g[i],moveCount*w[i]);
                silver += Math.min(s[i],moveCount*w[i]);
                sum += Math.min(g[i]+s[i],moveCount*w[i]);
            }
            if (gold>=a && silver>=b && sum>=a+b) {
                high = mid - 1;
                answer = Math.min(answer,mid);
            }
            else {
                low = mid + 1;
            }
        }
        return answer;
    }
}

 

1. 시간 범위 설정
   
   • 400000000000000L라는 구체적인 값으로 answer 및 end를 초기화
2. 이진 탐색의 구현
   • 각 도시의 트럭이 이동할 수 있는 총 횟수(moveCount) 계산 방식 차이 -> 추가 왕복을 가능한지 더 정확함
   • mid % (t[i] * 2L) >= t[i]를 확인하여, 남은 시간이 충분하면 moveCount를 하나 증가
3. 금, 은, 그리고 총 광물량의 계산 변수 간결화
4. 조건 검사 및 answer 갱신
   • 조건을 만족하는 경우(if (gold >= a && silver >= b && sum >= a + b))에 answer를 Math.min(answer, mid)를 사용하여 갱신 -> 효율적

 

---

 

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

프로그래머스