[프로그래머스] 86053 금과 은 운반하기 - JAVA(파라메트릭 서치)
문제
https://school.programmers.co.kr/learn/courses/30/lessons/86053
문제 분석
조건
여러 도시에 각각 일정량의 금`g`과 은`s`이 있다. 각 도시의 트럭은 한 번에 특정 무게`w`만큼의 광물을 특정 시간`t`을 들여 편도로 운반할 수 있다. 목표 지점에 금 `a`와 은 `b`를 모두 배달하기 위해 필요한 최소 시간을 구하는 문제
풀이방법
시간에 따라 트럭을 옮겨가며 계산하기엔 시간이 초과된다. 이 문제는 특정시간`time`동안 목표한 금과 은을 운반할 수 있는지를 확인하며 문제를 풀어야 한다. 이분탐색을 통해 시간을 줄여가며 배달이 가능한 최소 시간을 구하는 문제이다.
그리고 이렇게 특정 값을 정해두고 그 값이 답이 가능한지를 판단하며, 이분탐색으로 최적의 해를 찾는 것을 파라메트릭 서치라고 한다.
파라메트릭 서치와 이분탐
파라메트릭 서치가 꼭 이분탐색으로만 탐색하는 것은 아니나, 대부분의 경우에 이분탐색과 가장 궁합이 잘 맞는다고 한다.
그 이유는, 파라메트릭 서치는 조건 `A`가 가능하다면 `A`보다 좋은 조건에서는 무조건 가능하다는 단조성을 특징으로 갖는 문제에 적용할 수 있기 때문이다. 이 문제에서도 정답 시간보다 짧으면 절대 불가능하지만 정답 시간보다 길어진다면 전부다 배달이 가능하다는 특징이 있다.
이렇게 정답의 가능 여부가 명확히 나뉘는 범위에서 `가능`이 시작되는 경계값을 가장 효율적으로() 찾는 방법이 이분탐색이므로, 파라메트릭 서치는 이분탐색을 사용한다.
코드
class Solution {
public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
long maxTime = ((long) 10e9 * 2) * ((long) 10e5 * 2) + (long) 10e5;
long minTime = 1;
long mid;
long answer = maxTime;
while (minTime <= maxTime) {
mid = (maxTime + minTime) / 2;
if (check(a, b, g, s, w, t, mid)) {
maxTime = mid - 1;
answer = Math.min(answer, mid);
} else {
minTime = mid + 1;
}
}
return answer;
}
/**
* time 안에 금과 은을 다 옮길수있는지 확인하는 함수
*
* @param time
* @return
*/
public boolean check(int a, int b, int[] g, int[] s, int[] w, int[] t, long time) {
long sumGold = 0; // 모든 트럭이 옮길 수 있는 금의 합
long sumSilver = 0; // 모든 트럭이 옮길 수 있는 은의 합
long totalWeight = 0; // 모든 트럭이 옮길 수 있는 무게의 합
for (int truck = 0; truck < g.length; truck++) {
if (t[truck] > time) { // 트럭 편도 이동시간보다 목표한 시간이 짧으면 계산하지 않음
continue;
}
long round = (time - t[truck]) / (t[truck] * 2) + 1; // time 동안 왕복 가능 횟수 + 처음
long carrySum = round * w[truck]; // 트럭이 옮길 수 있는 최대한의 용량
// 최대 그 지역에 있는 자원만큼 옮길 수 있음
sumGold += Math.min(carrySum, g[truck]);
sumSilver += Math.min(carrySum, s[truck]);
totalWeight += Math.min(carrySum, s[truck] + g[truck]);
}
if (sumGold >= a && sumSilver >= b && totalWeight >= a + b) {
// 모든 트럭이 목표한 시간에 목표한 자원을 모두 옮길 수 있음
return true;
}
return false;
}
}