[Python] 백준 13305: 주유소

풀 듯 말 듯 못 풀었던 주유소문제이다.

그리디 알고리즘 문제인데, 현재 마을보다 저렴한 주유소까지만 기름을 사면 되겠다는 핵심 아이디어는 캐치했으나 구현에 어려움을 겪었다.
곧이곧대로 다음으로 싼 마을을 찾아 거기까지 거리를 구하고, 기름을 구매해서 다음 마을로 출발하는 방법을 선택했다. 코드는 역시 길어졌고 난잡해졌다.
구글에서 본 답안 코드는 다음과 같다.

n = int(input())
distance = list(map(int, input().split()))
town = list(map(int, input().split()))
min_price = town[0]
price = 0
for i in range(len(distance)):
    if min_price > town[i]:
        min_price = town[i]
    price += min_price * distance[i]
    
print(price)

코드가 간결하면서도 직관적으로 이해가 되진 않는다.
하지만 핵심 아이디어는 내 생각과 동일하다.

모든 마을을 지나가면서 가장 최근에 저렴했던 가격을 가지고 비교해본다. 만약 현재 마을의 기름 가격이 내가 가지고 있던 저렴한 가격보다 낮으면 기름을 교체해서 다시 앞으로 나아간다.

그러면 내가 처음 생각했던 다음 마을까지 거리를 찾아서 그 만큼의 기름을 사는 것과 동일한 결과를 낳는다.
차이점은 답안 코드는 기름을 미리 사지 않고 지나가면서 그 당시 필요한 만큼만 사는 방식이고, 내 코드는 출발 전에 기름을 충전한 뒤 출발하려했다는 점이다.

실패 후 성장

이번 문제 역시 생각대로 구현하다보니 코드가 난잡해졌다. 난잡해지면 오답일 확률이 높다는 것을 계속 생각하자!