[백준/Python] #13305 : 주유소 - 그리디

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

13305번: 주유소

 

처음에 문제를 제대로 이해를 못해서 접근을 잘못했었는데 생각하다보니 복잡해져서 결국 또 구글링 on.

 

 

Key Point는

• 각 도시 간의 거리를 모두 합한 값 = 주유해야 하는 양 (1km 이동 시마다 1리터 사용하므로)
• 최소 비용으로 주유를 해야하므로 기름값이 가장 싼 도시에서 주유를 많이 하면 좋은 것
• 처음에는 기름값이 싸든 비싸든 무조건 주유를 하고 시작해야 함
• 가장 싼 기름값을 변수에 저장해두고 각 도시를 지날 때마다 기름값을 비교해가면서 더 싸면 해당 변수에 갱신해야 함

참고한 블로그에서 설명을 잘해놔서 아래 링크를 첨부할 테니 직접 들어가서 보면 더 도움이 될 듯하다.

 

n = int(input())
distance = list(map(int, input().split()))
price = list(map(int, input().split()))

sum = 0
min_price = price[0]
sum += min_price * distance[0]
for i in range(1, n-1):
    if min_price > price[i]:
        min_price = price[i]
    sum += min_price * distance[i]

print(sum)

 

---

참고 : 

https://hongcoding.tistory.com/25

[백준] 13305 주유소 (Python 파이썬)