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

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

13305번: 주유소

 

 

import sys
n = int(sys.stdin.readline())
road = list(map(int, sys.stdin.readline().split()))
city = list(map(int, sys.stdin.readline().split()))
cost, res = city[0], 0 #1
for i in range(len(city)-1): #2
    if cost > city[i]: #3
        cost = city[i]
    res += cost * road[i] #4
print(res)

 

그리디 알고리즘을 이용하는 문제다. 가장작은 기름값으로 최대의 거리를 가서 최소 경비가 나오게 하는것이 목표인데 필자는 입력값으로 주어지는 기름값을 array[i] < array[i+1]로 구분하려고 고민해서 안풀렸었다. 예전에 이와 비슷한 풀이법을 본 기억이 있는데 기억이 가물가물해서 못푼것 같다. 단계별로 풀어보기 문제니까 문제번호 헷갈리지 않고 복습할 수 있을거라 생각한다.

 

#1 : 자동차가 처음엔 기름이 비어져 있는채로 시작한다 했으니 반드시 첫번째 기름가격을 이용해야한다.

#2 : 반복문에서 n-1까지 가는데 마지막 도시에서는 기름을 채우지 않아도 되니 n-1까지 반복한다.

#3, 4 : 반복문은 0부터 시작하지만 0은 조건문에 걸리지 않기 때문에 0번째 도시의 기름 값 * 다음도시까지의 거리로 처음이 정해지고 실제로는 다음 도시부터 조건문에 걸리는지 아닌지를 판단하게 된다.

 

*반복문을 돌려서 기름값이 다음 도시보다 저렴하지 않다면 갱신하지 않으면 된다.