[백준] 13305. 주유소 (python)

 

 

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

import sys

n = int(sys.stdin.readline())
distance = list(map(int, sys.stdin.readline().split()))
price = list(map(int, sys.stdin.readline().split()))

result = 0
now_price = price[0]
for i in range(n-1):
    now_price = min(price[i], now_price)
    result += now_price * distance[i]

print(result)

 

 

생각보다 어렵지 않은 문제였다.

1. 거리 정보와 리터 당 가격 정보를 각각 리스트에 저장한다.

2. 반복문을 돌면서 현재 가격과 다음 도시까지 남은 거리를 곱해 필요한 비용을 계산한다. 

3. 다음 도시에 방문했을 때, 리터 당 가격이 더 저렴하다면 더 저렴한 가격으로 기름을 구매하여 비용을 계산한다.

    (만약 더 저렴하지 않다면 이전 가격으로 구매한다. 이전 도시를 출발하기 전에 이미 구매했다고 해도 결과적으로는 똑같기 때문)

 

알고리즘 유형

• 그리디 알고리즘