📃 문제 설명

주유소

[문제 출처 : 백준]

👨‍💻 해결 방법

정말 말그대로 greedy하게 풀었다.

최소 비용으로 이동을 하려면,
다음 도시들의 기름값이 얼마인지 확인하고,
내가 더 비싸면, 이후 이동할 때 필요한 기름을
현재 주유소에서 다 넣고,
만약 현재 주유소보다 저렴한 곳이 다음 도시 중에 있다면,
우선 거기까지 갈만큼만 주유하고, 다음 도시에서 위 과정을 반복하면 된다.

1.현재 주유소의 기름값과 다음 도시의 기름값을 비교
1-1. 다음 도시가 더 싸면, 다음 도시까지 이동하는데 필요한 만큼만 주유
1-2. 다음 도시가 더 비싸면, 다다음 도시까지 이동하는데 필요한 만큼 주유하고 다다음도시의 기름값을보고 다다다음까지 갈지 다다음까지만 갈지 결정...

이런느낌으로 풀었다.
아마 아래 소스 코드를 보면 바로 이해할 수 있을듯!

👨‍💻 소스 코드

N = int(input())

 distances = list(map(int, input().split()))
 prices = list(map(int, input().split()))

 result = 0
 i = 0
 while i < N - 1:
     j = i + 1
     while prices[i] < prices[j]:
         result += distances[j] * prices[i]
         j += 1
         if j == N - 1:
             break
     result += distances[i] * prices[i]
     i = j

 print(result)