★그리디알고리즘★주유소[백준 파이썬 13305번]

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

13305번: 주유소

import sys

a = int(sys.stdin.readline())

b = list(map(int ,sys.stdin.readline().split()))

c = list(map(int, sys.stdin.readline().split()))

price = c[0]*b[0] #초기값
idx = c[0]
#print(idx)
for i in range(1, len(c)-1):
    #print(c[i])
    if c[i] < idx:
        # print("idx : {}".format(idx))
        idx = c[i]
        price += idx*b[i]
    else:
        price += idx*b[i]
print(price)

 

노드가 있을 때 

 

0 - 0 - 0- 0

1번째 노드의 초기값 설정을 해준다.

price = c[0] *b[0] ==> 리터당 기름값* (1번째 To 2번째 길이) 

 

for문을 통해 리터당 기름값이 싼거에 대해서 idx변수로 치환시킨다.

--> 만약 기름값이 앞에 도시보다 싸다? idx에 싼곳의 기름값 넣는다.

price 에 기름값과 도시간 거리로 가격 더하고

 

-->기름값이 앞의 도시가 싸다! idx 변환 시키지 말고 price에 기름값과 도시간 거리 곱하여 가격을 더한다.