백준 알고리즘 13305: 주유소(Python)

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

13305번: 주유소

---

문제 해결을 위한 과정

이 문제의 경우 그리디 알고리즘으로 해결할 수 있는 문제입니다. 그리디 알고리즘의 개념만 정확히 알고 있다면 쉽게 풀 수 있는 문제입니다. 가장 최선의 경우를 선택하는 경우 이기 때문입니다. 먼저 문제를 예를 들어봅시다. 

 

맨 처음 비용을 5로 잡았을때 다음 비용은 2 이므로 (5 < 2) 이 구간의 거리 즉 2만큼은 5라는 비용으로 이동합니다. 그 후 비용을 2로 갱신해줍니다.

5 * 2 = 10

 

비용을 2로 잡은 후 다음 비용은 4 이므로 (2 < 4) 이므로 다음 비용까지 비용 2를 유지합니다. 다음 비용은 1 이므로 갱신해 줍니다. 즉 3 + 1의 구간은 2라는 비용으로 이동합니다. 

2 * (3 + 1) = 8

 

비용은 1 이지만 마지막 구간이므로 종결합니다.

따라서 답은 10 + 8로 최소는 18입니다

---

소스코드

 

n = int(input())
route = list(map(int, input().split()))
amount = list(map(int, input().split()))
 
price = amount[0]
ans = 0
i = 1
ro = route[0]
while True:
  if i == n-1:
    ans += price * ro
    break
  if price < amount[i]:
    ro += route[i]
  else:
    ans += price * ro
    price = amount[i]
    ro = route[i]
  i += 1
 
print(ans)