알고리즘 백준 13305 주유소(파이썬)

알고리즘 백준 13305 주유소(파이썬)

백준 주유소 파이썬

백준 파이썬 주유소

 

코드

if __name__ == '__main__':
    import sys

    N = int(sys.stdin.readline())
    roadLength = list(map(int,input().split()))
    oilCost = list(map(int,input().split()))

    minCost = roadLength[0]*oilCost[0]  #첫번째꺼의 비용
    currentCost=oilCost[0]

    for i in range(1,N-1):
        if oilCost[i] < currentCost:  #여태까지 채워온 주유소가격(현재주유소가격)과 도착한곳의 주유소가격을 비교해서 도착한곳이 더 작으면
            currentCost = oilCost[i]  #현재 주유소 가격은 도착한곳의 주유소 가격으로 바꾼다
        minCost += currentCost*roadLength[i]  #앞으로 한칸 갈 정도의 도로길이는 현재주유소 가격으로 계산한다

    print(minCost)

 

문제풀이

0) 그리디 문제로 

       우선, 맨 처음엔 무조건 첫번째 주요소에서 다음의 갈 거리만큼 주유를 해야한다 -> roadLength[0]*oilCost[0]

 

       해당 문제에서의 핵심은 내가 여태까지 주유한 주유소의가격(currentCost)와 내가 도착한 주유소의 가격(oilCost)를 비교하여 더 작은 주유소 가격만(그리디) 남겨서 도로의 길이만큼 계산해 준다는 것이다

 

      또한 그 전 까지의 운행(가장 싼 주유소에 도착하기전)은 그 전에 주유소 가격들 중에서 싼 가격으로 주유를 해야하기 때문에 for문으로 주유소 가격을 비교하여 갱신하는 것이 필요하다!

 

 

       그다음엔 첫번째 주유소값(currentCost) 과 다음 주유소값(oilCost[i])를 비교하여 첫번째 주유소값(currentCost)가 크다면 첫번째 주유소값(currentCost)으로 다음 주유소 까지의 거리만큼 최솟값에 더해주고

      그게 아니라 다음 주유소값(oilCost[i])가 크다면 currentCost를 다음 주유소값(oilCost[i])로 바꾸어 주고 다음 주유소 까지의 거리만큼 최솟값에 더해준다

     이와 같은 방식으로 끝까지 for문으로 진행한다

 

깃허브

https://github.com/developer-hyun/Algorithm-Study/tree/main