문제 요약
새 도시 건설 장소로 금 akg과 은 bkg을 전달해야 한다.
각 도시는 금, 은 보유량과 한 대의 트럭을 가지고 있다. 트럭은 도시와 건설 장소 사이를 왕복하며, 한 번에 금과 은을 합쳐 최대 w[i]kg까지 운반할 수 있다.
가장 빠르게 목표 광물을 전달할 수 있는 시간을 반환한다.
핵심 아이디어
어떤 시간 time 안에 목표량을 운반할 수 있는지 판별할 수 있다면, 가능한 시간은 다음 성질을 가진다.
time초에 가능하다면, 그보다 긴 모든 시간에도 가능하다.따라서 가능 / 불가능의 경계를 이분 탐색하면 최소 시간을 찾을 수 있다.
시간 안에 가능한 이동 횟수
한 도시의 트럭이 편도에 t초 걸린다고 하자.
- 왕복 1회에는
2 * t초가 필요하다. - 마지막 운반은 건설 장소에서 돌아올 필요가 없으므로, 편도
t초만 남아도 한 번 더 운반할 수 있다.
move_count = time // (2 * t)
if time % (2 * t) >= t:
move_count += 1이 시간 동안 해당 트럭이 운반할 수 있는 총광물 최대량은 move_count * w다.
금, 은, 총광물을 따로 확인해야 하는 이유
도시마다 보유한 금과 은의 양이 다르고, 트럭의 운반 용량은 둘이 공유한다.
시간이 주어졌을 때 각 도시에서 운반할 수 있는 최대량을 더해 다음 세 조건을 모두 확인한다.
운반 가능한 금의 합 >= a
운반 가능한 은의 합 >= b
운반 가능한 전체 광물의 합 >= a + b예를 들어 금만 많이 운반 가능하고 은을 충분히 운반할 수 없다면 목표를 달성할 수 없다. 반대로 금과 은 각각의 합이 충분해 보여도, 트럭 용량이 공유되므로 전체 광물 합 조건도 필요하다.
풀이 과정
- 시간
time안에 각 트럭이 이동할 수 있는 횟수를 계산한다. - 도시별 운반 가능 금, 은, 전체 광물 최대량을 누적한다.
- 세 가지 조건을 모두 만족하면 해당 시간은 가능하다.
- 이분 탐색으로 가능한 최소 시간을 찾는다.
Python 코드
def solution(a, b, g, s, w, t):
def can_deliver(time):
total_gold = 0
total_silver = 0
total_mineral = 0
for gold, silver, capacity, one_way_time in zip(g, s, w, t):
move_count = time // (2 * one_way_time)
# 마지막 편도 이동으로 광물을 한 번 더 운반할 수 있다.
if time % (2 * one_way_time) >= one_way_time:
move_count += 1
transportable = move_count * capacity
total_gold += min(gold, transportable)
total_silver += min(silver, transportable)
total_mineral += min(gold + silver, transportable)
return (
total_gold >= a
and total_silver >= b
and total_mineral >= a + b
)
left = 0
right = 10 ** 15
while left < right:
mid = (left + right) // 2
if can_deliver(mid):
right = mid
else:
left = mid + 1
return left예시
금 10kg, 은 10kg이 필요하고 한 도시의 조건이 다음과 같다고 하자.
금 100kg, 은 100kg
트럭 용량 7kg
편도 시간 10초50초 동안 이동할 수 있는 횟수는 3회다.
10초: 첫 운반
30초: 두 번째 운반
50초: 세 번째 운반총 21kg을 운반할 수 있으므로 금 10kg과 은 10kg을 전달할 수 있다. 30초에는 최대 14kg만 운반할 수 있으므로 불가능하다. 따라서 최소 시간은 50초다.
시간 복잡도
N을 도시 수, T를 탐색 시간의 최댓값이라고 하자.
시간 하나를 판별할 때 모든 도시를 한 번 확인하므로 O(N)이다. 이분 탐색은 O(log T)번 수행된다.
- 시간 복잡도:
O(N log T) - 공간 복잡도:
O(1)
right = 10 ** 15를 사용하면 약 50회 이내의 이분 탐색으로 답을 찾는다.
정리
이 문제의 핵심은 시간 안에 운반 가능한 금, 은, 전체 광물량을 각각 계산하는 것이다. 마지막 편도 운반을 빠뜨리지 않고, 세 조건을 모두 확인하면 이분 탐색으로 최소 시간을 구할 수 있다.
