문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/86053
문제 설명
어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 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 함수를 완성해주세요.
제한사항
알고리즘: 이분 탐색
풀이
이 문제는 새로운 도시를 건설하기 위해 금 a kg, 은 b kg을 전달할 수 있는 가장 빠른 시간을 구하는 게 목표다.
시간이 오래 걸릴수록 금과 은을 더 많이 운반할 수 있다. 이 말은 즉 이분 탐색 풀이가 가능하다. ex) 3시간 -> 10개 운반, 4시간 -> 15개 운반, 5시간 -> 20개 운반 (시간별로 운반 개수가 오름 차순 졍렬됨. 이 중 최적의 시간을 찾는게 목표)
max_time이 (10^9 + 10^9) * 200000으로 이분 탐색이 최적이다.
그러면 여기서 mid_time으로 a, b를 운반할 수 있는지만 확인하면 된다. -> (possible 메서드)
내가 구현한 방법은 먼저 금을 우선적으로 운반한다. 금을 운반하고, 금을 다 운반하고도 더 운반할 수 있다면, 나머지는 은으로 채운다. 여기서 금을 우선적으로 운반했기 때문에 은은 최적으로 가져올 수 없다. 그렇기 때문에 현재 도시에서 가져간 금 개수와 바꿀 수 있는 은 개수를 체크해서 total_left_s에 더해준다. -> 예를 들면 우선적으로 금을 10개 가져갔을 때 은이 15개 남아있다면, 15개 중 10개는 금과 바꿀 수 있는 은 개수이다. 이 개수를 total_left_s에 더해준다.
그리고 모든 도시를 확인했으면, 이제 a, b를 충족시킬 수 있는지 확인한다.
만약 total_carry_g(금을 운반한 총개수)가 a보다 작다면 무조건 false다.-> 금을 우선적으로 옮겨줬기 때문에
이번엔 total_carry_g가 a보다 크거나 같고 total_carry_s가 b보다 작을 때를 확인한다.
total_carry_g가 a보다 크기 때문에 total_carry_g - a는 은으로 바꿀 수 있는 금 개수이다. 이때 total_left_s를 확인한다. total_left_s만큼은 금으로 바꿔도 가능한 은의 양이다. 하지만 a를 충족시켜야 하므로 total_carry_g - a만큼만 바꿀 수 있다. 마지막으로 바꿀 수 있는 최종 은의 개수를 체크한다.
long available_s = (total_carry_g - a) < total_left_s ? (total_carry_g - a) : total_left_s; // -> 바꿀 수 있는 최종 은의 개수
그리고 available_s + total_carry_s < b라면 a를 충족하면서 금을 은으로 최대한 바꿔도 b를 충족시키지 못하기 때문에 무조건 false다.
그 외 나머지는 true
위 방식으로 mid_time으로 운반이 가능한지 확인하면서, 이분 탐색을 이용하면 최적의 시간을 찾을 수 있다.
소스 코드
import java.util.*;
class Solution {
public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
long answer = -1;
answer = binary_search(a, b, g, s, w, t, (a + b) * 200000L);
return answer;
}
static long binary_search(int a, int b, int[] g, int[] s, int[] w, int[] t, long max) {
long min = 0;
while(min <= max) {
long mid = (min + max) / 2;
if(possible(a, b, g, s, w, t, mid)) {
//a, b 목표량 채웠으면 시간 줄이기
max = mid - 1;
} else {
//a, b 목표량 못채웠으면 시간 늘리기
min = mid + 1;
}
}
return min;
}
static boolean possible(int a, int b, int[] g, int[] s, int[] w, int[] t, long time) {
//먼저 골드부터 채운다.
long total_carry_g = 0;
long total_carry_s = 0;
long total_left_s = 0;
for(int i=0; i<g.length; i++) {
long carry_weight = time % (t[i] * 2) >= t[i] ? w[i] * (time / (t[i] * 2) + 1) : w[i] * (time / (t[i] * 2));
long carry_g = 0; //현재 지역에서 가져가는 금 개수
//금 먼저 옮기기
if(carry_weight >= g[i]) {
total_carry_g += g[i];
carry_g += g[i];
carry_weight -= g[i];
} else {
total_carry_g += carry_weight;
carry_g += carry_weight;
carry_weight = 0;
}
//나머지 은 옮기기
if(carry_weight >= s[i]) {
total_carry_s += s[i];
} else {
total_carry_s += carry_weight;
total_left_s += s[i] - carry_weight <= carry_g ? s[i] - carry_weight : carry_g; //현재 가져간 금 개수를 은으로 바꿀 수 있는 개수 카운트
}
}
if(total_carry_g < a) return false; //금을 우선으로 옮겼는데 미달이면 무조건 false;
else if(total_carry_g >=a && total_carry_s < b) {
//은만 미만일 때 가용할 수 있는 은의 개수를 구한다.
long available_s = (total_carry_g - a) < total_left_s ? (total_carry_g - a) : total_left_s;
if((available_s + total_carry_s) < b) return false; //가용 할 수 있는 은 + 토탈 은 < b 일 때 false;
}
return true;
}
}