백준 알고리즘 파이썬(Python) 13305번 주유소

---

 

일반적인 그리디 문제처럼 이문제에서 중요한 것은 리스트를 만들어 알맞은 값으로의 최신화이다

 

핵심은 왼쪽에서부터 순차적으로 도시의 기름값을 확인하여 min값을 최신화 해주는 것이다.

그리디의 핵심은 가장 최적의 경우를 탐색해 찾아내는 것

 

---

n = int(input()) #도시개수를 입력받는다.
road = list(map(int, input().split())) #도시 사이의 거리를 입력받는다.
city = list(map(int, input().split())) #도시의 기름값을 입력받는다.

min_val = city[0] #min_val 값을 첫 도시의 기름값으로
price_sum = 0 #price_sum 0으로 초기값 설정
for i in range(n-1): 
    if min_val > city[i]: #만약 city[i]의 값이 min_val 보다 작다면 이제 기존 min_val은 더이상 제일 작지 않으므로
        min_val = city[i] #이제 기존 min_val은 더이상 제일 작지 않으므로 새롭게 갱신
    price_sum = price_sum + (min_val*road[i])
print(price_sum)