파이썬 (python) 백준 13305 : 주유소

---

백준 13305 : 주유소

---

문제 내용

시간 제한 : 2 초

메모리 : 512 MB

 

문제

일직선 상의 n개 도시 순서대로 이동 (n: 2~10만)

- 노드 : 도시를 뜻하며, 숫자는 해당 도시에서의 기름값

- 간선 : 도시간의 도로길이 (1km이동 당 1리터 기름 사용)

입력

도시 개수 n

도로길이 순서대로 n-1개

주유소 리터당 가격 순서대로 n개

 

출력

모든 도시 이동하는 최소 비용

 

예제 입력 1 
4

2 3 1

5 2 4 1

 

예제 출력 1 
18

 

예제 입력 2
4

3 3 4

1 1 1 1

 

예제 출력 2

10

 

유형

• 그리디 알고리즘

---

풀이

이 문제는 그리디 알고리즘 문제이다.

기름값이 싼 도시에서 기름을 최대한 많이 구입하는게 이득이다.

 

이동을 위해 1번 도시에서는 무조건 기름 구매할 수 밖에 없다.

더 싼 가격으로 기름 구매할 수 있을 때까지 도시를 차례로 방문하며 도로길이 저장한다.

더 싼 도시가 나타나면 여태까지 저장한 도로길이*이전에 가장 싸게 구매할 수 있었던 기름값 으로 비용 계산 한다.

그리고 새로운 도시의 기름값으로 update 하고 위의 내용 반복한다.

import sys
n = int(sys.stdin.readline())
road_len = list(map(int, sys.stdin.readline().split()))
oil_price = list(map(int, sys.stdin.readline().split()))

cur_oil_price = oil_price[0]
total_price = 0
tmp_road_len = road_len[0]
for i in range(1, n-1):
    if cur_oil_price <= oil_price[i]:
        tmp_road_len += road_len[i]
    else :
        total_price += tmp_road_len * cur_oil_price
        cur_oil_price = oil_price[i]
        total_price += road_len[i] * cur_oil_price
        tmp_road_len = 0
        
if tmp_road_len != 0:
        total_price += tmp_road_len * cur_oil_price
print(total_price)