문제 개요
연료가 가득 찬 상태에서 각각 100km를 주행할 수 있는 바이크가 n대 있다고 가정해 봅시다. 이때 이 n대의 바이크를 활용해 이동할 수 있는 최대 거리를 구하는 것이 목표입니다.
여기서 모든 바이크는 동일하며, 1리터의 연료로 1km를 주행할 수 있다고 가정합니다. 만약 n대의 바이크가 같은 지점에서 출발해 나란히 주행한다면, 주행 가능한 거리는 단지 100km에 불과합니다. 따라서 핵심은 최소한의 연료 낭비로 최대 거리를 커버하는 것입니다. 연료 낭비를 줄인다는 것은 곧 실제로 사용하는 바이크 대수를 최소화한다는 의미이기도 합니다.
접근 방법: 직렬 운용과 연료 이송
바이크를 직렬로 운용하면 훨씬 더 먼 거리를 이동할 수 있습니다. 구체적으로는 마지막 바이크에서 다른 바이크로 일부 연료를 옮긴 뒤, 특정 지점부터 마지막 바이크를 더 이상 사용하지 않는 방식입니다.
그렇다면 어느 시점에 연료를 이송해야 할까요? 조건은 두 가지입니다. 하나는 최대 거리를 확보하는 것이고, 다른 하나는 연료를 받는 나머지 바이크들의 연료 탱크가 넘치지 않도록 하는 것입니다.
핵심 아이디어는 다음과 같습니다. 바이크 k대가 함께 주행하는 구간에서는 전체 연료 소비율이 k배가 되므로, 각 구간별로 이동 가능한 거리는 fuel / k가 됩니다. 이를 n대부터 1대까지 차례로 더하면 됩니다.
알고리즘 단계
covered_distance := 0으로 초기화합니다.n > 0인 동안 반복합니다.covered_distance := covered_distance + (fuel / n)n := n - 1
covered_distance를 반환합니다.
즉, 최종 결과는 연료량 × (1 + 1/2 + 1/3 + ... + 1/n) 형태의 조화급수(Harmonic Series) 합이 됩니다.
예제 코드
아래 파이썬 구현을 통해 더 쉽게 이해할 수 있습니다.
def maximum_distance(n, fuel):
covered_distance = 0
while (n > 0):
covered_distance = covered_distance + (fuel / n)
n = n - 1
return covered_distance
n = 3
fuel = 100
print(maximum_distance(n, fuel))입력
3, 100
출력
183.33333333333334
결과 분석
n = 3, fuel = 100인 경우 계산 과정은 다음과 같습니다.
- 첫 번째 구간: 3대가 함께 주행 → 100 / 3 ≈ 33.33km
- 두 번째 구간: 2대가 주행 → 100 / 2 = 50km
- 세 번째 구간: 1대가 주행 → 100 / 1 = 100km
합계는 33.33 + 50 + 100 = 약 183.33km로, 세 대를 단순히 나란히 몰았을 때의 100km보다 훨씬 멀리 이동할 수 있음을 확인할 수 있습니다. 시간 복잡도는 O(n)으로 매우 효율적입니다.