[백준] 13305 주유소 (Python 파이썬)

www.acmicpc.net/problem/13305

13305번: 주유소

문제 설명

N개의 도시가 일렬로 나열되어 있고, 각 도시간의 거리를 입력받는다.

그리고 그 도시에서의 리터당 주유비를 입력받는다.

이 때, 도시의 시작점에서 끝지점까지 이동하는데 드는 최소의 비용을 구하면 된다.

---

풀이 과정

각 도시마다 주유소의 가격이 다르기 때문에, 최소의 비용으로 최대충전을 하는 것이 목표다.

이 때, 시작점에서는 반드시 주유가 되어있어야 하기 때문에 첫 최소비용은 시작점의 가격으로 시작한다.

이동을 하다가, 현재의 가격보다 저렴한 도시를 발견하게 되면, 그 지점에서 충전을 이어서 하면 되고

현재 가격보다 저렴한 도시가 나타나지 않는다면, 현재 가격으로 계속 충전하면 된다.

 

혹여나, "미리 충전을 해야하는데 어떻게 이동중에 전 가격으로 충전을 하냐"고 생각을 할 수 있는데

for문을 통해 dis[i]는 계속해서 다음 이동 거리로 변하는 상황이고

다음 최저 가격이 등장하기 전까지는 이전 최저가격을 저장하고 있는 상황이기 때문에 이 방법이 가능하다.

코드를 보면 더 이해하기 쉬울 것이다.

n = int(input())

dis = list(map(int, input().split()))
price = list(map(int, input().split()))

minPrice = price[0]
ans = 0
for i in range(n-1):
    if minPrice > price[i]:
        minPrice = price[i]
    ans += minPrice * dis[i]

print(ans)

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !