13305 주유소

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline
N = int(read())
distance = list(map(int,read().split()))
oil = list(map(int,read().split()))

now_oil_cost = oil[0]
total = now_oil_cost * distance[0]

for i in range(1,len(distance)):
    next_oil_cost = oil[i]
    if next_oil_cost < now_oil_cost :
        # 도착한 도시의 기름 값이 현재보다 더 작으면 갱신하자.
        now_oil_cost = next_oil_cost
    # 기름값이 작지 않으면 갱신하지 않고 거리와 곱해지고,
    # 기름값이 작으면 갱신되서 거리와 곱해지고 비용을 더한다.
    total += now_oil_cost*distance[i]

print(total)

3. 문제 풀이

이 문제는 처음엔 점화식을 세워야하나..? 싶었다. 그러나 다시 생각을 해보니 굳이 그럴 필요가 없었다.

문제 해결 방법은 굉장히 간단한 아이디어에서 나온다. 내가 도착한 도시의 기름값이 이전에 있던 도시보다 싸면 이 기름을 채워야하므로 기름을 갱신해준다. 싸지 않다면, 이전 도시에서 기름을 다다음 도시까지 갈 수 있게 채워 넣어주는게 더 싸다. 따라서, 매번 기름값들을 한번씩 확인해서 갱신해주고 거리와 곱해주면 해결된다.