기름통 무제한
도로 이동할 때, 1km마다 1리터 사용
도로 위 숫자 = 길이(1km -> 1리터)
원 안에 숫자 = 리터당 가격(x원 * n리터 = xn원) => 충전하는 식으루 생각
total = 6일 때,
1. 5 6 = 30원 한번에 다 채운 경우
2. (5 2) + (2 3) + (4 1) = 20원 갈 때마다 채운 경우
3. (5 2) + (2 4) = 18원 큰값에서만 필요한만큼만 챙기고 나머진 싼데서 한번에
쌀때 많이 사두는게 그리디하게 좋음
마지막 주유소에선 사지 않는다
맨왼쪽부터 이중for문같이 갈건데
일단 맨앞에 주유소의 기름값을 가진 변수 j(=가장 싼 주유소임 -> 인덱스를?)
for(range(1, n))이동하면서 다음 주유소와 기름값 비교 -> 다다음 주유소와도 비교
(i-1 vs 1)가 아니라
(j vs i vs i+1 vs i+2 vs ... ) 인거임
핵심은 이거
road 인덱스랑 station 인덱스랑 따로 감
road[] # range(n-1)
station[] # range(n)
gas = 0 #<-- 충전 필요
필요한 총리터 tot_gas = sum(road)
최적의 해 ans = station[0] * tot_gas #첫 번째 주유소에서 다 넣는 경우를 max로 넣어둠
for i in range(1, len(station)):
# 다음 주유소가 더 싸면
if
tmp = (station[i-1]*road[i-1]) + (station[i]*total)
ans = min(ans, tmp)
print(ans)
'''내가 푼'''
n = int(input())
road = list(map(int, input().split())) # range(n-1)
station = list(map(int, input().split())) # range(n)
tot_gas = sum(road) # 필요한 총 gas 수
#ans = station[0] * tot_gas # worst case : 첫 번째 주유소에서 다 넣는 경우 금액
gas = road[0] # 보유 가스 (1리터에 5원 -> 2k라면 10원 필요)
min_gas_idx = 0
now_road_idx = 0
ans = 0
for i in range(1, n):
# 다음 주유소가 더 싸면
tot_gas -= road[min_gas_idx]
gas -= road[min_gas_idx]
ans += (station[min_gas_idx] * road[now_road_idx])
if station[min_gas_idx] > station[i] or gas == 0:
min_gas_idx = i
now_road_idx = i
print(ans)
'''내가 푼 - 다시'''
n = int(input())
road = list(map(int, input().split())) # range(n-1)
station = list(map(int, input().split())) # range(n)
ans = road[0] * station[0] # 무조건 계산되는 값 (for문은 비교를 위해 1부터 시작할 것임)
min_cost_idx = 0
for i in range(1, n-1):
# 앞에 min값보다 작다면
if station[min_cost_idx] > station[i]:
min_cost_idx = i
ans += (road[i] * station[min_cost_idx])
print(ans)
링크 : https://alpyrithm.tistory.com/134