13305: 주유소

주유소는 각 도시별 리터당 가격과 거리를 고려했을 때 최소 비용을 계산하는 문제이다.

핵심은 가장 리터당 가격이 낮은 도시를 찾아서 남은 거리만큼 필요한 기름을 모두 구매하고 해당 도시까지 가는데 필요한 기름 구매 비용의 최솟값을 합산하면 된다.

이 문제를 풀면서 몇 가지 실수를 했었는데 먼저 채점 결과를 보면 다음과 같다.

처음 코드를 구현하고 나서 17점을 받았을 때 뭐가 문제인지 한참 헤맸던 것 같다.

알고보니 예제 입력을 테스트 케이스로 코드를 구현하다보니 최소 비용이 드는 도시는 한참 뒤에 있음에도

앞에서 그 비용을 모두 계산해버린 것이다. 즉 최소 비용이 드는 도시까지 가는 비용을 생각하지 못했다...

 

다시 코드를 수정하고 최소 비용이 드는 도시까지 가는 비용 + 해당 도시에서 남은 거리만큼의 기름 전부 구매를 하는 방식으로 결과 값을 계산했는데 이번에는 58점이 나왔다...

 

서브태스크 표에는 획득하지 못한 42점이 '기존 제약조건 이외에 아무 제약조건이 없다'고 해서

제약 조건을 다시 살펴보니 N이 100,000 까지로 제한이 되어있다.

아무래도 시간 초과 문제인 것 같아서 구현한 코드의 시간 복잡도를 계산해봤는데 몰랐던 사실을 발견했다.

 

기존 코드에는 Python의 List 중 min을 계산하는 함수를 반복문 내에서 사용했었는데

이게 O(N)의 복잡도를 가진다고 한다. 여기서 N은 len(list) 이기 때문에 리스트의 사이즈가 클수록 커진다.

결국 내가 구현했던 코드는 의도치 않게 O(N^2)의 시간 복잡도를 가지고 있었던 것이다.

(참고: Complexity of Python Operations)

 

그래서 min을 사용하는 대신 인덱싱을 하면서 값을 비교하는 방식으로 리터당 가격이 제일 작은 도시를 찾아서 계산하도록 알고리즘을 변경했더니 100점을 받을 수 있었다.

 

n = int(input())
 
road_length = list(map(int, input().split()))
oil_price = list(map(int, input().split()))
 
total_price = 0
 
oil_price = oil_price[:-1]
min_oil_price = min(oil_price)
min_oil_price_idx = oil_price.index(min_oil_price)
 
idx = 0
cur_min = oil_price[0]
for price in oil_price:
  if cur_min > price:
    cur_min = price
 
  total_price += road_length[idx] * cur_min
  idx += 1
 
print(total_price)