📖Problem

🔍Intuition

🔍Approach

🚩My submission

❌첫번째 시도 → 17점

import sys
input = sys.stdin.readline

# 초기화
n = int(input()) # n: 도시의 개수
road = list(map(int, input().split())) # 도로의 길이
oil_price = list(map(int, input().split())) # 리터당 가격

current = road[0] * oil_price[0] # 현재 기름
good = road[0]
for i in range(1, len(road)):
    if road[i] * oil_price[i-1] <= road[i] * oil_price[i]:
        if road[i] * oil_price[i-1] <= road[i] * good:
            good = oil_price[i-1]

    else:
        if road[i] * oil_price[i] <= road[i] * good:
            good = oil_price[i]
    current += good * road[i]
print(current)

주유소 리터당 가격을 비교해서 이동할 때마다 어떤 주유소를 주유할지 결정하는 로직으로 구현했으나 결과는 17점이 나왔다.

왜 이게 문제일까 했는데, 내 코드는 기름을 채우는 시점에서의 최저 가격이 아니라 각 도로의 길이에 따른 비용을 단순히 비교하고 있고, 도로의 길이를 기준으로 최소 가격을 추출을 했는데 길이보다는 리터당 기름 가격이 최소 비용을 찾는데 중요한 요소인 점이 코드에 드러나지 않았다.

✅두번째 시도 → 100점

따라서 불필요하게 도로의 길이를 매번 연산하지 않고 현재 리터 가격과 가장 작은 주유소의 리터 가격을 비교하여 더 작으느 리터 가격을 저장해두고, 이 가격과 거리를 최종 연산한다.

1. 도시의 개수를 n, 도로의 길이를 road 리스트, 각 도시의 리터당 가격을 oil_price 리스트에 저장을 하고, 최저 비용인 min_cost는 0으로, 도시의 기름 가격을 나타내는 min_price는 첫 번째 도시의 기름 가격으로 초기화한다.
2. 각 도시를 순회하며, 다음 도시로 이동하는데 필요한 기름 비용을 계산한다,
   1. 현재 도시에서의 기름 가격과 최소 가격을 비교하여 더 작은 값을 최소 가격 min_price로 갱신한다.
   2. 최저 비용 min_cost에 최소 가격과 현재 도로의 길이를 곱한 값을 누적하여 계산한다.
3. 최종 결과인 min_cost를 출력한다.

import sys
input = sys.stdin.readline

# 초기화
n = int(input()) # n: 도시의 개수
road = list(map(int, input().split())) # 도로의 길이
oil_price = list(map(int, input().split())) # 리터당 가격

min_cost = 0 # 최저 비용
min_price = oil_price[0] # 첫번째 도시의 기름 가격

for i in range(n - 1):
    if oil_price[i] < min_price:  # 현재 도시에서의 기름 가격이 최소 가격보다 작으면 갱신
        min_price = oil_price[i]
    min_cost += min_price * road[i] # 현재 도시에서 다음 도시로 이동할 때 드는 비용을 추가

print(min_cost)