문제

title: "코딩테스트 연습 - 금과 은 운반하기"
image: "https://image.freepik.com/free-vector/landing-page-template-for-a-website_23-2147782747.jpg"
description: "어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다."
url: "https://school.programmers.co.kr/learn/courses/30/lessons/86053"

문제 풀이

문제 접근

  • 이분탐색으로 시간을 두고, 적절한 mid를 찾으면 된다.
  • 시간을 조금 썼던 부분은, 최댓값 지정이였다.
    • 금과 은, 그리고 이동거리를 따졌을때, 나오는 최대 시간으로 하면 모든 케이스들을 통과할 수 있다.

      간단한 수도 코드 정리

      Type/Paste Your Code

풀이 코드

class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        long answer = -1;
        long left = 0;
        long right = (long) (1e9 * 2 * 1e5 * 2);
        
        while (left <= right) {
            long mid = (left + right) / 2;
            
            // 해당 시간 내에 운반할 수 있는 금과 은의 총합
            long totalGold = 0;
            long totalSilver = 0;
            long totalAll = 0;
            
            for (int i = 0; i < g.length; i++) {
                // mid 시간 내에서 왕복
                long tripCount = mid / (2 * t[i]);
                
                // 편도 체크
                if (mid % (2 * t[i]) >= t[i]) {
                    tripCount++;
                }
                
                // 트럭 운반 최대량
                long maxTransport = tripCount * w[i];
                
                // 금, 은 운반 가능량
                long transportGold = Math.min(g[i], maxTransport);
                long transportSilver = Math.min(s[i], maxTransport);
                
                // 금, 은 합쳐서 계산
                totalGold += transportGold;
                totalSilver += transportSilver;
                totalAll += Math.min(g[i] + s[i], maxTransport);
            }
            
            
            // 금, 은 만족하는지 검사
            if (totalGold >= a && totalSilver >= b && totalAll >= (a + b)) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        
        return answer;
    }
}