금과 은 운반하기

문제 정보

• 문제 링크
• 난이도: Lv.3
• 문제 유형: 탐색

풀이

이진 탐색을 이용해서 풀어야 하는 문제다.¹

가장 빠른 시간을 직접 구하는 것이 불가능하므로, 어떤 $T$ 시간 내에 필요한 금과 은을 모두 옮기는 것이 가능한가? 라는 관점에서 접근해야 한다.

그리고 어떤 $T$ 시간 안에 옮길 수 있다면 그 보다 작은(빠른) 범위에 대해서. 옮길 수 없다면 그보다 큰 범위에 대해서 이진 탐색을 수행해 최종적으로 금 $a$ kg과 은 $b$ kg을 전달할 수 있는 가장 빠른 시간을 구할 수 있다.

필요한 값

가불가를 판단하기 위해서는 다음 3가지 값이 필요하다.

1. $T$ 시간 동안 최대로 옮길 수 있는 금의 양
   • 주어진 시간 동안 금을 $a$ kg 옮길 수 있는지 판단하기 위함이다.
   • 이 값이 $a$ 미만이라면 그건 시간이 더 필요하다는 의미.
2. $T$ 시간 동안 최대로 옮길 수 있는 은의 양
3. $T$ 시간 동안 최대로 옮길 수 있는 광물(금 + 은)의 양

이 중 3) $T$ 시간 동안 최대로 옮길 수 있는 광물의 양이 필요한 이유는 다음과 같다.

트럭	$T$ 시간 동안 옮길 수 있는 금의 양	$T$ 시간 동안 옮길 수 있는 은의 양
1	10	10

위와 같은 상황에서 필요한 금/은의 양이 모두 10kg으로, 총 20kg의 광물이 필요하다고 가정해보자.

그렇다면 1) $T$ 시간 동안 옮길 수 있는 금의 양, 2) $T$ 시간 동안 옮길 수 있는 은의 양은 만족한다. 그러나 3) $T$ 시간 동안 옮길 수 있는 광물의 양 또한 10kg으로, 주어진 시간 내에 필요한 광물을 모두 옮길 수 없다. 그렇기에 3) $T$ 시간 동안 옮길 수 있는 광물의 양 또한 필요한 것이다.

시간 내에 옮길 수 있는 광물의 양

그럼 $T$ 시간 동안 옮길 수 있는 양을 계산하는 방법을 살펴보자.

옮길 수 있는 양 자체는 ”$T$ 시간 동안의 운반 횟수 × 운반 가능한 광물의 양($w$)“으로 계산된다.

그러므로 $T$ 시간 동안의 운반 횟수만 구하면 최대로 옮길 수 있는 양을 계산할 수 있다.

그리고 문제에서 각 도시에 트럭 한 대가 있다고 했다. 다시 말해 트럭은 도시에서 출발한다. 즉, 1번은 편도 이동으로 광물을 운반할 수 있다. 그 이후에는 광물을 운반하기 위해서는 도시와 광물 장소를 왕복해야 한다.

이걸 뒤집어서 생각해보면 최대로 왕복한 후 남은 시간이 편도 이동에 드는 시간보다 많으면 한 번 더 운반할 수 있다는 것이다.

그렇기에 $T$ 시간 동안의 운반 횟수는 다음과 같다.

$$\{\begin{array}{ll}T÷2t& T\mathrm{mod}2t<t\\ T÷2t+1& T\mathrm{mod}2t\ge t\end{array}$$

이진 탐색 범위

이진 탐색을 수행하기 위해선 탐색 범위를 설정해야 한다.

우선 low는 문제의 제한사항 상 a, b가 모두 0일 수 있으므로 0이다.

high는 가장 오래 걸리는 경우이므로 a, b 모두 $10^9$이고, $w=1,t=10^5$인 경우이다.

이 경우 필요한 광물을 모두 전달하는 데 필요한 시간은 다음과 같다.

• 금을 전달하는 데 걸리는 시간 = $2\times 10^5\times 10^9$
• 은을 전달하는 데 걸리는 시간 = $\{2\times (10^9-1)\}\times 10^5+1\times 10^5$
• $\therefore$ high = $4\times 10^{14}$

코드

import java.util.*;
 
class Solution {
	public long solution(int a, int b, int[] g, int[] s, int[] w, ing[] t) {
		long low = 0;
		long high = (long) 1e14 * 4;
		long answer = high;
		
		while (low <= high) {
			long mid = (low + high) / 2;
			
			if (isPossible(a, b, g, s, w, t, mid)) {
				answer = Math.min(answer, mid);
				high = mid - 1;
			} else
				low = mid + 1;
		}
		
		return answer;
	}
	
	private boolean isPossible(int a, int b, int[] g, int[] s, int[] w, int[] t, long timeLimit) {
		long maxGold = 0;
		long maxSilver = 0;
		long maxMineral = 0;
		
		for (int i = 0; i < g.length; i++) {
			long roundTime = 2 * t[i];
			long moveCnt = timeLimit / roundTime;
			
			if (timeLimit % roundTime >= t[i])
				moveCnt++;
				
			long maxDeliver = moveCnt * w[i];
			
			maxGold += Math.min(g[i], maxDeliver);
			maxSilver += Math.min(s[i], maxDeliver);
			maxMineral += Math.min(g[i] + s[i], maxDeliver);
		}
		
		return (maxMineral >= (a + b) && maxGold >= a && maxSilver >= b);
	}
}

Footnotes

1. 파라메트릭 서치를 쓴다고도 하는데, 나는 해당 용어에 대해 회의적인 입장이므로 일단 이진 탐색으로 서술해둔다. ↩