알고리즘💻/그리디
BOJ 13305번: 주유소
호프
2021. 8. 3. 22:23
https://www.acmicpc.net/problem/13305
13305번: 주유소
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1
www.acmicpc.net
현재 위치한 도시에서의 리터당 가격이 다음 도시의 리터당 가격보다 비싸면 사야하는 최소한의 양(다음 도시까지 가는 데 필요한 양) 만큼만 구입하고, 현재 위치한 도시에서의 리터당 가격이 다음 가야하는 곳 보다 싼 경우에는 현재 가격보다 더 싼 도시가 나타날때까지의 거리를 가는 데 필요한 리터만큼 구입한다.
import sys
input = sys.stdin.readline
N = int(input())
road = list(map(int, input().split()))
cost = list(map(int, input().split()))
ans = 0
buy = 0
now = cost[0]
for i in range(1, N):
buy += road[i-1]
if (now > cost[i]):
ans += now * buy
buy = 0
now = cost[i]
ans += buy * now
print(ans)