(JAVA) 금과 은 운반하기

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

프로그래머스

풀이

이분 탐색과 Parametric Search를 사용한 풀이이다.

Parametric Search는 특정 상황을 만족하는 특정값의 최대 혹은 최댓값을 구하는 최적화 문제에 적용할 수 있음을 생각하고, 이 알고리즘을 이번 문제에 적용할 생각을 하는 것이 중요하다.

 

Parametric Search는 최적화 문제를 결정 문제로 바꾸는 것이다. 이번에 풀이한 '금과 은 운반하기' 문제를 예시로 들면 원래는 "새로운 도시 건설을 위한 모든 금과 은을 전달하는 최소 시간을 구하시오" 라는 최적화 문제였지만, 이를 "현재 가정한 시간 내에 모든 금과 은을 전달할 수 있는가?"라는 결정 문제로 해결해야한다는 것이다.

 

이론상 최대 시간과 이론상 최소 시간의 중간값부터 시작하여, 이분 탐색을 통해 최종적으로 모든 금과 은을 시간 내에 전달할 수 있는 최소 시간을 찾으면 된다.

class Solution {
    public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
        long answer = (long) (2 * 10e9 * 2 * 10e5); // 이론상 최대 시간으로 가정
        long min = 0; // 이론상 최소 시간
        long max = (long) (2 * 10e9 * 2 * 10e5); // 이론상 최대 시간
        
         while (min <= max) { // 이분 탐색 시작
            long mid = (min + max) / 2; // 중간값
            long gold = 0;
            long silver = 0;
            long add = 0;
             
            // 전체 도시를 순회하며, 시간 내에 옮길 수 있는 금과 은의 양과 총 양(add)를 더해주기
            for(int i = 0; i < g.length; i++) {
                int curGold = g[i];
                int curSilver = s[i];
                int curWeight = w[i];
                int curTime = t[i];

                long iter = Math.round(mid / curTime / 2.0);
                
                gold += Math.min(curGold, iter * curWeight);
                silver += Math.min(curSilver, iter * curWeight);
                add += Math.min(curGold + curSilver, iter * curWeight);
            }
            // mid 시간 내에 모든 금과 은을 전달할 수 있을 경우
             if (a <= gold && b <= silver && a+b <= add){
                 max = mid - 1;
                 answer = Math.min(mid, answer);
                 continue;
             }
             // 그렇지 못한 경우
             min = mid + 1;
         }
        return answer; // 탐색이 끝났으면 결과 반환
    }
}