요즘 또 그리디가 풀리지 않는다 ,,,

1. 다른 풀이

import sys
input = sys.stdin.readline

n = int(input())
roads = list(map(int, input().split()))
costs = list(map(int, input().split()))

res = roads[0] * costs [0]
minimum = costs[0]

dist = 0

for i in range(1, n-1):
    if costs[i] < minimum:
        res += minimum * dist
        dist = roads[i]
        minimum = costs[i]
    else:
        dist += roads[i]
    
    if i == n-2:
        res += minimum * dist
        
print(res)

풀이출처: https://alpyrithm.tistory.com/134

영 갈피를 못 잡겠어서 결국 답을 봤다.
생각보다 그렇게 어렵지 않은 풀이였는데,

• 제일 처음 시작하는 값: 내가 다음 도시까지 갈 수 있도록 기름 만땅 채워넣기
• 현재 costs 값을 가장 작은 값이라고 가정
• dist는 최소값인 기름값에 모든 거리를 다 곱해줄 것이기 때문에 필요한 변수!
• 그 다음 도시부터 돌면서
  • 만약 현재 우리가 최소값이라고 잡아둔 값보다 cost[i] 가 작다면, 일단 지금까지 온 거리인 dist까지의 값과 기름값을 곱해 최종값에 더해주고, dist는 그 다음 거리로 초기화 시켜준 후, cost[i]로 minimum 역시 바꿔준다.
  • 만약 작지 않다면 계속해서 roads 값을 dist에 더해주기!

2. 마치며

아직 그리디를 졸업하려면 한참은 남은듯하다 ^^...