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

문제 설명

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

문제 풀이

• 결정 함수 구현이 좀 복잡한 이분 탐색문제였다.
• 이분 탐색은 시간을 기준으로 동작시켰고 시간의 최소값은 0, 최대값은 20억(a+b의 최대값) * 20만(운반시간*왕복2회) = 400조가 된다.
• 시간을 기준으로 이분탐색을 진행할 때 특정 시간이 주어졌을 때, (a,b)만큼 조달이 가능한지를 판별하는 함수 구현이 필요하다.
• 해당 함수로직은 다음과 같다.

  • 모든 도시에 대하여 다음 3가지 항목의 누적값 구하기
    - 해당 시간에 옮길 수 있는 금,은 최대 무게 (total)
    - 해당 시간에 옮길 수 있는 금 최대 무게 (totalG)
    - 해당 시간에 옮길 수 있는 은 최대 무게 (totalS)
  • 다음 3가지 조건을 만족하는 경우 특정 시간에 (a,b)만큼 조달 가능하다.
    - total >= a + b
    - totalG >= a
    - totalS >= b

소스 코드 (JAVA)

import java.util.*;

class Solution {

    //특정 시간이 주어졌을 떄, (a, b)만큼 조달이 가능한지 리턴
    //가능하면 ture
    //불가능하면 false
    public boolean isPossible(long time, int a, int b, int[] g, int[] s, int[] w, int[] t) {
        int n = g.length;
        long total = 0L;
        long totalG = 0L;
        long totalS = 0L;

        for (int i = 0; i < n; i++) {
            //해당 시간에 옮길 수 있는 횟수
            long cnt = time / (2L * t[i]);
            if (time % (2L * t[i]) >= t[i]) cnt++;

            //해당 시간에 옮길 수 있는 무게
            long tmp = Math.min(cnt * w[i], g[i] + s[i]);
            //각 도시의 총합 최대 무게 누적
            total += tmp;
            //각 도시의 금 최대 무게 누적
            totalG += Math.min(tmp, g[i]);
            //각 도시의 은 최대 무게 누적
            totalS += Math.min(tmp, s[i]);
        }

        if (total >= a+b && totalG >= a && totalS >= b) return true;
        return false;
    }

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

        //이분 탐색
        while(lo + 1 < hi) {
            long mid = (lo + hi) / (long)2;

            if (isPossible(mid, a, b, g, s, w, t)) hi = mid;
            else lo = mid;
        }
        return hi;
    }
}