[백준 - Python] 13305. 주요소 (그리디)

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

13305번: 주유소

 

코드

import sys
n = int(input())
road = list(map(int, sys.stdin.readline().split()))
city = list(map(int, sys.stdin.readline().split()))

price = city[0]
liter = road[0]
cost = 0
for i in range(1, n):
    if price > city[i] or i == n-1:  # 더 져렴한 도시 도착한 경우 or 마지막 도시까지 도달한 경우
        cost = cost + liter * price
        price = city[i]
        liter = 0
    if i == n-1:  # n-1인 경우의 road는 없으므로
        break
    liter += road[i]

print(cost)

 

현재 주요하는 도시 이후에, 리터당 가격이 현재 도시보다 저렴한 도시가 존재하는지 확인하고

더 저렴한 도시가 있다면, 해당 도시에 도달하기까지 필요한 만큼만 주유를 하고

더 저렴한 도시가 없다면, 끝까지 도달할 수 있을 만큼 주유를 한다는 아이디어로 문제를 풀었다.

 

다시 말해,

현재 주유소보다 리터 당 가격이 저렴한 도시까지 도달하는데

이동해야 하는 거리만큼만 현재 주유소에서 주유를 하면 된다.

 

각 주유소를 돌면서 주유소의 오른쪽 도로의 이동 거리를 liter 변수에 더해준다.

 

더해주면서 주유소를 한 칸씩 이동해 가는데,

price에 저장되어 있는 리터당 가격보다 저렴한 주유소에 도달한 경우에,

지금까지의 이동 거리를 이동하기 위해 드는 비용을 cost에 저장하고

주유소의 리터당 가격인 price를 업데이트 해준다.

 

주유 가격은 더 저렴한 주유소에 도달했을 때 이외에도

마지막 주유소에 도달한 경우에도 계산해 주어야 하기 때문에,

조건식에 i == n - 1인 경우도 같이 조건으로 걸어준다.

 

또한 i == n - 1의 주유소에는 오른쪽 도로가 없으므로

liter += road[i] 가 불가능하다.

따라서, 해당 코드 이전에 반복문을 탈출한다.