[백준] 13305 주유소

✔️ 문제 링크

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

💡 핵심 아이디어

1️⃣ 가는 길은 하나밖에 없음으로 가는 길 마다 기름이 싼 도시에서 더 기름이 싼 도시까지 가지 위해 기름을 충전하는 것이 가장 싼 가격에 목적지까지 갈 수 있는 방법이다.

⭐️ 소스 코드

from collections import defaultdict

if __name__ == '__main__':
    N = int(input())
    city_len = [0] + list(map(int, input().split()))
    city =  list(map(int, input().split()))

    ans_dict = defaultdict(int)
    temp = city[0]

    for i in range(1,len(city)):
        ans_dict[temp] += city_len[i]
        if temp > city[i]:
            temp = city[i]

    ans = 0
    for k in ans_dict.keys():
        ans += (k * ans_dict[k])

    print(ans)