## 🌟 문제
[코딩테스트 연습 - 금과 은 운반하기 \| 프로그래머스 스쿨](https://school.programmers.co.kr/learn/courses/30/lessons/86053)
여러 도시에서 트럭을 이용해 금 `a kg`, 은 `b kg`을 새로 건설할 도시로 운반해야 한다. 각 도시 i에는 금 `g[i]`, 은 `s[i]`가 있으며, 해당 도시와 건설 장소를 왕복하는 트럭 1대가 있다.
트럭은:
- 편도 이동 시간 `t[i]`
- 최대 적재량 `w[i]`
- 금과 은을 합쳐서 적재 가능
- 여러 번 왕복 가능
모든 트럭을 최적으로 운행했을 때, 금 `a kg`과 은 `b kg`을 모두 운반하는 데 필요한 최소 시간을 구하는 문제
## 🌟 풀이
### 이 문제는 이분탐색으로 풀어야 한다!
이 문제는 **답을 구하는 문제가 아닌 답인지 아닌지를 확인하는 문제**이다.
무슨말이냐면, 어떤 경로를 거쳐야 최단 시간 안에 운송할 수 있는지를 구하는게 아닌, 어떤 시간 안에 어떻게든 운송이 가능한지만을 확인하는 문제라는 것이다.
그리고 **단조성**을 띈다.
**단조성은 어떤 시점을 기준으로 가능/불가능, 정답/오답이 갈리는 특징을 말한다.**
이 문제 역시 아래와 같은 특징을 가지므로 단조성을 갖고 있다.
- 어떤 시간 Time에서 운송이 가능하면 그보다 더 큰 시간들에서는 (가능한 트럭의 왕복 횟수가 증가하기 때문에) 무조건 시간 안에 운송이 가능하다.
- 어떤 시간 Time에서 운송이 불가능하면, 그보다 더 작은 시간들에서도 (가능한 트럭의 왕복 횟수가 감소하기 때문에) 시간 안에 운송이 불가능하다.
따라서 **이 문제는 이분탐색으로 풀어야 한다!**
### 운반 가능 여부 확인하는 check 함수 구현하기
`check(time)` 함수는 time 시간이 주어졌을 때 운반이 가능한지를 확인하는 함수이다.
check 함수에서 확인해야 하는 조건은 아래 3가지 조건이다.
1. 모든 도시에서 time 시간 안에 실을 수 있는 금의 총 합 >= a (필요한 금의 양)
2. 모든 도시에서 time 시간 안에 실을 수 있는 은의 총 합 >= b (필요한 은의 양)
3. 모든 도시에서 time 시간 안에 실을 수 있는 광물(금과 은)의 총 합 >= a + b
1번, 2번 조건은 금이나 은 자체가 부족한 경우를 막는 조건이다. time 시간 안에 트럭은 충분히 운송할 수 있더라도 전체 도시들에 있는 총량이 필요한 양보다 작으면 불가능하기 때문에 이 부분을 체크하기 위한 조건이다.
마지막 3번 조건은 트럭이 두 광물을 동시에 실어야 하기 때문에 확인해야 하는 조건이다. 1번, 2번 조건을 확인할 때에는 같은 트럭 용량을 두 조건이 각각 최대로 사용하고 있기 때문에, 동시에 싣는 것이 불가능할수도 있다. 따라서 동시에 가능한지도 함께 확인하는 것이다.
그래서 `check(time)`의 구조는 모든 도시를 돌면서 아래 3가지를 구해서 확인하는 식으로 되어 있다.
1. 그 도시가 time 시간 안에 새 도시에 보낼 수 있는 최대 금
2. 그 도시가 time 시간 안에 새 도시에 보낼 수 있는 최대 은
3. 그 도시가 time 시간 안에 새 도시에 보낼 수 있는 최대 광물
이것을 구하려면 time 시간 안에 트럭이 몇번 새 도시에 도착할 수 있는지를 구해야 하는데, 중요한 것은 운반이 "도착" 시점에 이뤄진다는 것이다. 그래서 기본적으로는 왕복 시간을 이용해서 횟수를 구하되, 딱 한번 새 도시로 편도로 갈 수 있는 여유 시간이 남는다면 한번 더 운송하도록 해야 한다. 코드로 구현하면 아래와 같다.
```javascript
const maxDeliveries = Math.floor(time / (2 * t[i])) + (time % (2 * t[i]) >= t[i] ? 1 : 0);
```
### 이분탐색 구현하기!
check 함수까지 구현했으니 이제 이분탐색만 하면 된다. 이건 간단하니까 그냥 코드만 남겨둔다.
```javascript
// 이분탐색
let left = 0, right = 10 ** 15;
while (left < right) {
const mid = Math.floor((right + left) / 2);
if (check(mid)) right = mid;
else left = mid + 1;
}
```
## 🌟 코드
```javascript
function solution(a, b, g, s, w, t) {
// time 시간 안에 모든 도시에서 필요한 광물들을 운반할 수 있는지를 확인
function check(time) {
const cityCount = g.length;
let gold = 0, silver = 0, total = 0;
for (let i = 0; i < cityCount; i++) {
// time 시간 안에 "운반"할 수 있는 최대 횟수
const maxDeliveries = Math.floor(time / (2 * t[i])) + (time % (2 * t[i]) >= t[i] ? 1 : 0);
// time 시간 안에 운반할 수 있는 광물의 최대 양
const cap = maxDeliveries * w[i];
gold += Math.min(g[i], cap);
silver += Math.min(s[i], cap);
total += Math.min(g[i] + s[i], cap);
}
return gold >= a && silver >= b && total >= a + b;
}
// 이분탐색
let left = 0, right = 10 ** 15;
while (left < right) {
const mid = Math.floor((right + left) / 2);
if (check(mid)) right = mid;
else left = mid + 1;
}
return left;
}
```
> 이진탐색 문제 재밌다... 취향에 맞음