[백준 13305번] 주유소 - 파이썬

 

문제 링크:

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

13305번: 주유소

 

 

문제 풀이:

이 문제의 핵심은 거리에 상관없이 도시마다 최소한의 가격으로 도시를 지나가야 한다. (현재 상황에서 지금 당장 좋은 것만 고르는 기법인 그리디 알고리즘 문제에 해당) 

• 전 주유소보다 현 주유소가 가격이 싸다면 현 주유소에서 충전 (처음 기름 충전은 첫 도시에서 해야 하므로 반복문 전에 변수 m을 만든다) 
• 이를 토대로 반복문을 이용하여 도로를 건너야 한다.

 

---

# 13305번 주유소

n = int(input())
city_road = list(map(int, input().split()))
liter_price = list(map(int, input().split()))

ans = 0
m = liter_price[0]

# 현 지역의 주유소 가격이 전 지역의 주유소 가격보다 저렴하면 현 지역에서 주유 
for i in range(n-1):
  if liter_price[i] < m:
    m = liter_price[i]
  ans += m * city_road[i]
  
print(ans)

 

[백준 13305번] 주유소 - 파이썬